Efficient Sampling on Riemannian Manifolds via Langevin MCMC
Authors: Xiang Cheng
Jingzhao Zhang
Suvrit Sra
Venue: NeurIPS 2022 Accept (2022)

Abstract:   We study the task of efficiently sampling from a Gibbs distribution $d \pi^* = e^{-h} d {\text{vol}}_g$ over a Riemannian manifold $M$ via (geometric) Langevin MCMC; this algorithm involves computing exponential maps in random Gaussian directions and is efficiently implementable in practice. The key to our analysis of Langevin MCMC is a bound on the discretization error of the geometric Euler-Murayama scheme, assuming $\nabla h$ is Lipschitz and $M$ has bounded sectional curvature.  Our error bound matches the error of Euclidean Euler-Murayama in terms of its stepsize dependence.  Combined with a contraction guarantee for the geometric Langevin Diffusion under Kendall-Cranston coupling, we prove that the Langevin MCMC iterates lie within $\epsilon$-Wasserstein distance of $\pi^*$  after $\tilde{O}(\epsilon^{-2})$ steps, which matches the iteration complexity for Euclidean Langevin MCMC. Our results apply in general settings where $h$ can be nonconvex and $M$ can have negative Ricci curvature. Under additional assumptions that the Riemannian curvature tensor has bounded derivatives, and that $\pi^*$ satisfies a $CD(\cdot,\infty)$ condition, we analyze the stochastic gradient version of Langevin MCMC, and bound its iteration complexity by $\tilde{O}(\epsilon^{-2})$ as well.

Efficient Sampling on Riemannian Manifolds via Langevin MCMC
Xiang Cheng
Jingzhao Zhang
Massachusetts Institute of Technology x. chenggberkelee.... edu edu
Tsinghua University jzhzhang@mit.cc edu edu
Suvrit Sra
Massachusetts Institute of Technology suvritSmit.. edu
Abstract
We study the task of efficiently sampling from Gibbs distribution dr¹ e=ddvoly over Riemannian manifold via (geometric) Langevin MCMC: this algorithm involves computing exponential maps in random Gaussian directions and is efficiently implementable in practice. The key to our analysis Langevin MCMC is bound on the discretization error of the geometric Euler-Murayama scheme, assuming Vi. is Lipschitz and M has bounded sectional curvature. Our emor bound matches the error of Euclidean Buler-Murayama in terms of its stepsize dependence. Combined with a contraction guarantee for the geometric Langevin Diffusion under Kendall-Cranstee coupling, prove that the Langevin MCMC
iterates lie within Wasserstein distance of n²" after ((s-2) steps, which matches the iteration complexity for Euclidean Langevin MCMC. Our results apply in general settings where can be nonconvex and M can have negative Ricci vature. Under additional assumptions that the Riemannian curvature tensor has bounded derivatives, and that n² satisfies CD(,, oo) condition, we analyze the stochastic gradient version of Langevin MCMC, and bound its iteration complexity by ((s=2) as well.
Introduction
Stochastic differential equations (SDEs) offer powerful formalism for studying diffusion processes, Brownian motion, and algorithms for sampling and optimization. We study in particular the following geometric stochastic differential equation:
dx(t)) ((x(t) + dB)
(1.1)
that evolves on d-dimensional Riemannian manifold (M,g). g)- Analogous to the Euclidean setting, the map / - Ty M denotes drift (T₃ M is the tangent space standard Brownian motion on A [Hsu, 2002, Ch. 3]. The notation in (1.1) is a shorthand; we can define (1.1) more precisely as the unique diffusion process whose generator is the operator Lf
M), and dB3 denotes the
(V B) + fAf, where A is the saplace-Beltrane operator (see [Hsu, 2002, Proposition. 3.2.1]).
When the drift (xx) = - Vh(()) (the gradient is taken w.r.t. the manifold metric), the SDE (1.1) has an invariant distribution nt with density e eh(x),, with respect to the Riemannian volume measure (x); for M = d with metric g(æ) = I, this reduces to the familiar result for Euclidean Langevin diffusion. Using the Kendall-Cranston Coupling technique (Chapter 6.5, Hsu [2002)) together with carefully constructed Lyapunov function by Eberle [2016], we can quantify the mixing rate for (1.1)
in the 1- Wasserstein distance (w.rt. the manifold distance) under suitable regularity conditions.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

However, the exact SDE is not implementable in practice, so we consider an MCMC algorithm using the Geometric Euler- Murayyma (Piggott and Solo, 2016, Muniz et al., 2021] discretization of (1.1):
1k+1 = Exp., (6.((x)) + Voca),
(1.2)
where Exp,, denotes the exponential map for M, and Ça is a standard Gaussian with respect to any orthonormal basis of T2. M. It has long been known that the discrete-time process (1.2) converges to the SDE (1.1) in the limit as 5 + 0 [Gangolli, 1964, Jørgensen, 1975, Hsu, 2002].
Motivation for studying the SDE (1.1)
Geometric SDEs such as (1.1) play a crucial role in the design and analysis of MCMC algorithms [Girolami and Calderhead, 2011, Patterson and Teh, 2013] that have had much success solving Bayesian problems on statistical manifolds. Recently, it has been shown that the mirror Langevin Algorithm on the Hessian manifold of a function can be significantly faster than its Euclidean counterpart [Zhang et al., 2020, Chewi et al., 2020, Li et al., 2022, Gatmiry and Vempala, 2022].
These SDEs also directly relate to the tasks of sampling and optimization on manifolds, where often a Lie group structure helps capture symmetries (e.g.. the Grassmann manifold, SO(n), (n)) etc.) [Moitra and Risteski, 2020, Piggott and Solo, 2016, Muniz et al., 2021]. Furthermore, in Lee and Vempala [2017, 2018), the authors propose fast algorithms for constrained sampling and volume estimation on polytopes by sampling from the Hessian manifold of a barrier function.
2 Overview of Main Contributions
Our first contribution in this paper is to provide a quantitative, non-asymptotic bound on the discretization error between (1.1) and (1.2). We present this bound in Lemma 1 in Section In our bound, the seateeedssuurddddiitttt
between a single step of (1.2) and (1.1) over ó time is bounded by O(8%). This 8 error scaling matches that of Euler Murayama in Euclidean space [Durmus and Moulines, 2017]. We highlight that our bound is entirely explicit, and depends polynomially on dimension, sectional curvature of M, and the Lipschitz parameter for B quantittis which are intrisic to the manifold, and invariant to the choice of coordinate system.
Two recent papers. (Wang et al., 2020, Li et al., 2022] also look into a similar problem of bounding the discretization error of (1.2). Wang et al. [2020] analyze the error of (1.2), but rely on uniformly bounding certain derivatives of the densities along the sample path (see Assumption [Wang et al., 2020]); even in Euclidean space, it is not clear whether such bound exists, and whether it depends only polynomially on parameters such as dimension. Li et al. [2022] provide a quantitative bound on the bias of (1.2) on Hessian manifolds; they assume a bound on "modified self-concordance" parameter that is not affine invariant and can be made arbitrarily large.
We discuss Lemma 1 in more detail, and sketch its proof in Section 4. The proof relies on a careful construction of geometric Langevin Diffusion as the limit of (1.2), and may be of independent interest.
Our second contribution is show that after Ö(e-2) steps, the distribution of (1.2) is within 1- I-Wasserstein distance from the stationary distribution of (1.1). We present this result in Theorem 1. This dependence matches that of Euclidean Langevin MCMC [Durmus and Moulines, 2017].
The Ô in our iteration complexity hides polynomial dependency on dimension, sectional curvature, Lipschitz-parameter of 3. and 1 1/0, where a can be viewed as "mixing rate of the exact SDE." " Theo- rem 1 requires that 3 satisfy manifold analog of the distant-dissipatiiity assumption (Assumption 2 with m > L 2. where - Ric is a lower bound on the Ricci curvature of A2). Assumption is general enough to include cases when 3 - V for some nonconvex h or when M has negative Ricci curvature. The catch is that in such cases, 1/a can become very large; this is generally unavoidable, even on Euclidean space. Euclidean Langevin diffusion for non-log- non-log-concave concave distributions [Eberle, 2016, Bou-Rabee et al., 2020, Gorham et al., 2019, Cheng et al., 2020].
assumption has often been used in the analysis of
We highlight a computational sub-contribution that (1.2) only requires computing exponential maps in the direction of 3 plus a uniform Gaussian direction. In many cases, exponential maps are efficiently computable, and this Theorem leads to a computationally efficient sampling algorithm. Our analysis extends naturally if one replaces (1.2) by retraction step; if the retraction is of order 3/2

---

or higher, the one-step error still scales as O(6²). The question of how to construct good retraction maps is well studied in literature, and is somewhat orthogonal our main objective, so we do not provide details here, and instead refer readers to [Absil and Malick, 2012, Absil et al., 2009].
Recently, Ahn and Chewi [2021], Gatmiry and Vempala [2022], Li and Erdogdu [2020] have considered a different discretization of (1.1), where one assumes that the endpoint of the geometric Brownian motion dB² can be sampled exactly (so that only the drift 3 is discretized). Sampling the exact geometric Brownian motion can be done efficiently in special settings such as the sphere [Li and Erdogdu, 2020], but on a general manifold, this can be much more expensive than computing an exponential map; in such settings the Langevin MCMC algorithm based on (1.2) may be prefereable. We do highlight, however, that a number of the above results provide error bounds in KL-divergence, which is tighter than the Wasserstein bound in Theorem 1.
We discuss assumptions and consequences of Theorem 1 in more detail and sketch its proof in Section 5. The proof essentially combines our discretization analysis with a mixing result for (1.1) based on the Caaadt--rrnnnoon coupling and Lyapunov function from [Eberle, 2016].
For our third contribution, we analyze the manifold analog of SGLD [Welling and Teh, 2011];
2k41 Expx, x. (xxx(I)) + vo(x),
(2.1)
The the difference between (2.1) and (1.2), that at each step, ,3 is replaced by a random vector field 3g which satisfies: (i) Bl = 3; and (ii) [1,x (x) - (1x) I a almost surely. We show that after Ö( ?) steps, (2.1) is within e-2- Wasserstein distance from the stationary distribution of (1.1); thus the dependency does not degrade when replacing & by its stochastic estimate. We present this result in Theorem 2. For this analysis, we require Assumption 2, with m > TRie/2 and R = O: this is a more restrictive condition than Theorem 1; when /
Vh, this restriction is equivalent to the CD oo) condition [Bakry et al., 2014]: 4 Ric > O, where Ric is the Ricci curvature tensor!.
Though restrictive, the CD((, oo) class of distributions is nonetheless interesting; it is the manifold analog of the class of log-concave densities on Euclidean space, and sampling from this class has been a topic of much recent interest. In machine learning, the stochastic estimate of / can often be computed much more quickly than the exact 8, e-g., when 3 52 where f is the empirical average of some loss over a large number of observations. In such cases, (2.1) can be much faster than (1.2). In Section 6 we discuss the assumptions and consequences of Theorem in greater detail.
Though Theorem requires more restrictive assumptions than Theorem 1, its proof differs from the proof of Theorem 1 in significant way: we show mixing of the discrete-time process directly (instead of relying on mixing of the exact SDE). This approach is necessary in order to take advantage of the fact that 3g is an unbiased estimate B. The key intermediate result for showing mixing under (2.1) is Lemma 29. We believe this lemma to be of independent interest as it quantifies the distance evolution between two arbitrary discrete-ting -icre stochastic processes (that may be unrelated to Gaussian noise and Brownian motion). As an example, Mangoubi and Smith [2018] showed that ball walk mixes quickly on manifolds with positive sectional curvature. Using Lemma 29, one can show the more general statement "ball walk mixes quickly on compact manifolds with positive Ricci curvature."
3 Preliminaries: Key Assumptions and Notation
We state in this section the four key assumptions of this paper. Our first assumption involves lower bounding Ricci curvature of the manifold M. Let Ric denote the Ricci curvature tensor: Assumption 1. We assume that for all x E M, u, u E T,M M, Ric(u, u) 2 Liie for some L E RR
Intuitively, the more positive the Ricci curvature (i.e. the smaller the value of LRie), the faster geometric Brownian motion mixes.
Our second assumption is a natural generalization of the distant-dissipati condition in the Eu- clidean setting. It helps ensure that the drift traps the variable within a bounded region. For any x, E M, let d(xr, y) denote their Riemannian distance.
Assumption 2. We call a vector field 3 (m, q, Re--disaat-diisipativ if there exist constants m > O. R 2 0, and g E R such that, for all x, y satisfying d(z,)) w) 2 R, there exists minimizing geodesic
note that 3 1//WWh, therefore m is 1/2 times ttrong-convent parameter of h.
3

---

7: [0, + M with 7(0) = x and (1) = y. such that the inequality
(T(() y + 2) - // /()) I =mdd(zy))
holds, where [(: x) denotes parallel transport from TyM M along v. In addition, for all I, satisfying d(x, y) S R, there exists a minimizing geodesic [0, 1] + M with y(0) x and 7(1) y, such that we have instead the inequality
(T (B)))) > =) ((x), S gd(xxy)²
For some intuition: a strictly convex function will have m > 0, R 0, and & arbitrary. Note that we do not require a unique geodesic between 2, y-
For some intuition about Assumption 2: in the Euclidean setting, the first condition sim- plifies to (B(y) - 3(z), y =) S -mlly =112- and the second condition simplifies to (8(y) - 3(x), =²) S <lly x112
We need our third and fourth assumptions for bounding the discretization enror of (1.2). Assumption 3 upper bounds the Lipschitz constant of 3: Assumption lower bounds sectional curvature of M. Assumption 3. A vector field L/3- Lly-iipschitz if. for all e M and all M, [V,,(x)]| s
In the (flat) Euclidean setting, Assumption 3 is equivalent to saying that ((x) being a L/3 Lipschitz vector field.
Assumption 4. Let R be the Riemannian curvature tensor of the manifold M. We assume that there exists LR E R such that for all E M, and for all u, v, w, z T,M, (R(u, v)e, u) S |R||u|||||||]?
We now introduce additional notation that will be used throughout this paper. We assume some background in Riemannian geometry, and freely use standard notation; we refer the reader to [Jost, 2008, Lee, 2006, Petersen, 2006] for an in depth treatment. Readers may also find some works on Riemannian optimization useful as additional context: [Bacák, 2014, Udriste, 2013, Absil et al., 2009, Zhang and Sra, 2016, Boumal, 2022].
We use V to denote the Levi Civita connection. Given æ. y E M and T,M, we use I(;;; x - y) to denote parallel transport of from to y along their minimizing geodesic (if such a choice is not unique we will specify); we sometimes also use the more concise alternative notation T
T T( + y). Given general curve (possibly non-geodesic) Y [0. 1] - M, we will also use (1)" denote the parallel transport of v from 7(0) 7(1), along 7-
A basis F of the tangent space T.MM at some point E M is an ordered tuple (F).... ..... Fd) of vectors that span T.M. We use [' x + y) := (T(F";; + y).. x - y)) to denote the ordered tuple of parallel transport of the each of the basis vectors in F. Given e E Rd and basis F of some M, we use v F' as shorthand for Σi= F.. A distribution that we will see frequently in this paper is the one given by E o E", where & &~ ~N, I) is random vector in Rd, and x E M and Ex an orthonormal basis of M. We use N2 I) to denote the distribution of & E". One can verify that (2, /) does not depend on the choice of basis F.".
3.1 An illustrative example: sampling from a sphere
To give some intuition about Assumptions 1 4, we present simple example for sampling from 5d-1 the unit d-sphere in Rd, which is a positively curved Riemannian manifold." The subsequent bounds for the Sd case also generalize with minor modifications to other closely-related manifolds such as (O)d).
Let (xx): : Rdd > Re be potential function, and suppose that we wish to sample from dp(x:) xx U(()) duol defined over dd11, known that for any x 1d-1, v E T,M, Ric(v, v) >
'The sphere is one of the special cases when Brownian motion can be efficiently sampled exactly, and so if one's actual goal is to sample from a sphere, prior work such as Li and Erdogdu [2020] provide a better algorithm and analysis.

---

so that Assumption is satisfied with LRie O. The sectional curvature is bounded by 1, so that Assumption holds with R 1. For the remainder of this example, for S we will identify T2 M. with {u E Rd of x 0}. Since the sphere is a submanifold of IRd, the metric is simply given by the Euclidean dot product, i.e. gu, v) u''v.
Next, we will verify Assumption Let us assume that for all on the sphere, U(x) satisfies [+)())] S In and \>((())]| I L2 where V and 4 are the usual Fuclidean gradient and Hessian respectively (bolded to distinguish from V, the covariant derivative). In order to sample from dp(x). B(x) = (1 xxx' xx')vV"'' (x)). It is known that geodesic 7(t) corresponds a great are on the sphere, and that parallel transport of a vector v involves a rotation of the tangential component of St and u, V E T.M such that ||
v. To be precise, for any coordinates, V.V = (uu")y )u. Thus ( (wu (I - rx (U(x) + (²U(z)u S L1 + L2. Thus Assumption 3 holds with L'g L1 L2-
verify that, in Cartesian
Finally, we will verify Assumption 2. Since Sd-1 has diameter т, the first part of Assumption 2 is satisfied with arbitrary and R = The second part of Assumption 2 is satisfied with q L'g. This is because di (T(3(7(0);7()) + (0)) ((((0)),~'00)) z (1(7()),7(11)) (Vr())(((())) (t)) S (t))
Bounding the Discretization Error in Geometric Euler-Murayama
One of our main technical contributions is an error bound for the Euler-Murayama discretization. We provide an informal statement of this error bound as Lemma 1 below, and provide the formal statement as Lemma in Appendix A.3.
Lemma 1 (Informal version of Lemma 7). Let xxl) denote the solution to (1.1) initialized at some (0). Let x (t) denote one step geometric Euler Murayama discretization: x²) == ExPr(o) (x3()())) + VtC), where <~ >~x (). Under Assumptions 3 and 4, for sufficiently small t, there exists a coupling between x(t) and x (t) such that
=[d(=((),,x(0)) x 5 O(1"),
where O() hides polynomial dependence the Lipschitz constant L'g. the sectional curvature of M, and dimension d.
Proof Sketch for Lemma 1
Given time interval T, we construct a sequence of processes (z)( indexed by (exact definitinion given in (4.2) below). Marginally, each x²' (f) corresponds the linear interpolation of sequence of Euler-Murayama steps with stepsize 5' = 2-iT. More specifically, for k E Z+,
x = ExPat (o' + V
C Nog (0,
x'(t) = Exp,g t- ('= (5' + vo((1)
for t E [R:6", (I. + 1)6*]
Notice that for i = 0, x (T') is a single step of (1.2) with stepsize T. On the other hand, zxt) == lim;- x² (L) is exactly the SDE in (1.1) (see Lemma at the end of this section). We will soon see that ([d(x'(T)) x (T)) 88) We can then bound E Eid(x" (T),
2T()) 0 by summing over the pairwise distance between adjacent x and 2++1 for Z (this diminishes geometrically). This proves Lemma 1.
To bound the distance between x² and f+11, we introduce crucial additional structure: adjacent pairs of processes (#t, =f+1) are coupled using the manifold analog of synchronous coupling, together with the discrete-time analog of "rolling without slipping". (see Remark 1),
The exact formula for how 25+1 is to be constructed from zi is given in (4.1) below; it is little dense, so we provide pictorial illustration in Figure 1. For simplicity, we assume that B = (the dominating error in Lemma I is due to Brownian motion). Figure I takes place over period of time from kdt (k: + 1)6² (equivalently, 2k8 to (2k: + -)) The black squiggle denotes (B(t)- B(ks*)) )) E for [K8*, (I: + 1)6*}, where B(t) is standard d-dimensional Brownian
5

---

motion, and E is some basis at zt. Let bj. = (B((k + 1)6") B(ko")) o E (black solid arrow).
Bounding the distance between x' and pi+1 consists of two steps:
Figure 1: An illustration of the coupling between paths for of and +++ when 3 = over the time interval [A:8*, 1)
Step 1: Bounding : Exp,,t (b + x22 1)) [Solid black arrow vs dotted black arrow] The purple line represents the geodesic from 5i to =26"" by construction, the basis Egg is the parallel transport of Ex along the purple geodesic. The dotted black arrow denotes the (B((k + 1)0") - B(k)²)) o Eigh: we verify that it the paralle transport of bj. (black arrow) along the purple geodesic. Using Lemma 28, we can bound the distance between 2i41 = Exp,; (b)) (gray point) and Exp,,t (T(b; af 1) (green point) as
(xp)), E[d(Exp Expail (T(b): ot + + 1)> S (1 O(Lndd)) )) "
Step Bounding d d(Exp,,t) (T (b/b - x + 2 [Dotted black arrow vs blue red arrow] Let
b2t = (B((2: + 1) - B(2k8 E
1++ 2--1 = (B(22 + 2)0++1) - B((2k + 1)8 )) Ei+1
We verify that (b6) oj + 2+1 (black dotted arrow) equal to g6+1 + b (note that gi+1 1/28"), On the other hand, 22 (orange point) is obtained from taking step in b direction (blue arrow) followed by a step in the [bb this is not the same as taking a single step in the bj. = byt + 22k+1 direction (green point). However, we can bound the distance between the orange point and the green point using Lemma 3 of Sun et al. [2019] (restated as Lemma 38 for ease of reference):
i++
-> xx direction (red arrow). Due curvature,
bi+1 +b
E[d(Exp,,. 44 (T(b); o + 2 ))) 2 < 0(1 11 22
b [[
+ | (1) (((5))3)
Summing the bounds of Step 1 and Step 2 gives E(d(ai+ 22t+2) ) v 0LD Eld (1t 1 Eld(at) + 1
(((5))). Recursing over k = 0...2', and assuming that T S Lnd we get E[d 2 i+1
)
E[d(x' (T), a (()) 08) Summing over i = 0.. gives E(d(x (T),
Details for Construction of Brownian Motion
To bound the discretization error, we first characterize the manifold SDE (1.1) as the limit of family
of random processes. Let M be an initial point and E = {E. ..... Ed) be an orthonormal basis of T Too. Let B(t) denote a standard Brownian Motion in Rdd. Let T R Define
T To:
= 2 = Expag (T3(=)) + (B(T) - B(0) Eg)

---

For any i E Zt, let 8 := TT We will now define points T E M and orthonormal basis Eg of T = for all and all ls E (0.....7/67 Our construction is inductive: Suppose we have already defined #x and Eg for some and for all & E {O..... T/8". :0.....7/6') Then, construct 2t"! for all = {0............... (08...,///++1, as follows:
00= vo: Foo = F.,
3 26+1 EXP 1 (1 + (B((2k + 1)8 B(2k) E
2x+11 = I 122k + +22++1)
2k+2 = ExP 16-+13(=22) ((x22+1) + (B((2k: + 2) B((2k + 1)0+t))) Fizttl)
22++2 = r(Ek - 22k+2)
++1
(4.1)
The above display defines points ix i+1 for all k- = (o....,7//*** 7/8t+1. For parallel transport, the minimizing geodesic is not unique, any arbitrary choice will do. We verify that for any
i, for all k, = is indeed of the form (1.2), i.c. x/+1 ExPat (8'5(x1) vo where S == 1. (B((k + 1)0") - B(k)') o E ~ Nag (0. Finally, for any i, any k, and any Jo
e [ko', (k + 1) we define x' (t) to be the "linear interpolation" of 2t and 1
x' (t) = Expst (+ (8 B(xk) + (B((k + 1)6") B(kk))) EX).
(4.2)
Remark 1. The choice of basis Ej in (4.1) can be seen as combination of "synchronous cou- pling" and "rolling without slipping" (see Chapter 2 of [Hsu, 2002]). In particular, E
=f + = corresponds to "synchronous coupling" step from z 10//1 is (roughly) parallel to the step from o to 2 On the other hand, E == P ;
1+1 + i+1 1) corre-
:22k
/+1 is with respect to orthonormal sponds to "rolling without slipping" step from 1224+1 to 22222
basis that is parallel- srrullel-transported from 2+1 to #2k+11
.++1
We verify in the following Lemma that the limit, i + oc, of xf (f) is the SDE (1.1):
Lemma 2. For any T, for E [), let xxt) == lim, x' (t). This limit exists uniformly almost- surely, and r²t) is a diffusion process generated by the operator whose action on any smooth function f is given by L. (V (3) + {JA,,, where A denotes the Laplace Beltrami operator. Thus xt)) is equal to (1.1) in distribution.
Lemma 2 follows immediately from [Gangolli, 1964, Jørgensen, 1975], but we provide proof in Appendix A.1 for completeness.
5 Langevin MCMC on Riemannian Manifolds
With the one-step discretization error in Lemma 1, we can bound the iteration complexity of Langevin MCMC (1.2):
Theorem 1 (Convergence of Langevin MCMC on Riemannian Manifold). Assume the manifold M satisfies Assumptions 1 and 4. Assume in addition that there exists a constant L'n such that for all (this last assumption is
E M, u, v, w, E M,M, ((V R) (u, vyw, z) S L' [ |||||||||=/|||||||||| for analytical convenience; L'n does not show up in the quantitative bounds). Let / be a vector field satisfying Assumptions 2 and 3; assume in addition that >> LRie/2 /2 and that q + LRie/2 2 O. Let x² be some point with ((x*) = O.
Let y(t) denote the exact geometric SDE given in (1.1) initialized at some y(O). Let K E Zz be some iteration number and 8 be some stepsize. Let Iy denote the Euler Murayama discretization of (1.1), defined by Tk+1 Expay, (85(z)) + V8CK), where So Naz (0, I), initialized at some Do satisfying d(zo; x²) < 2R.
Then, there exists a constant Co = poly(L d, LR, R, m-Lunc72 72 log K), such that if < t. then there is coupling between vk and y( K5) sulisfying the distance bound
Ejd(y(KS)) e -aKôtlyt Lnu /2 E(d(((()) zo)l + exp ((g + LRie/2) - 0(82/2)
7

---

Ô hides polynomial dependence on L'g. d, Lg, R, 1 L log K, log 1 8 and
a :=
min
m- LBie
16
2R
We defer the proof of Theorem I to Appendix A.4, where we state the explicit expressions for Co.
Discussion of Theorem
To sample from (x)) = e dvolgg) we let B(x) == - Vh(x); under this choice of 8, (x) is invariant under the SDE for y().. Picking s(() x xx)), we thus ensure that Law(y(t)) TT" for all t. Therefore, the W1 distance between Law(xx) and x' is upper bounded by 5)d()((K))
which in turn upper bounded in Theorem 1.
The distance bound consists of two terms: the first term is exponentially small in Kō, so it goes to 0 as the number of steps tends to infinity; the second term is proportional to 62/2, We first pick 8 = Ō(=2) ) so that the second term is bounded by E. It then suffices to let K ad log [Eld((())=m ) + (q + 2 Ō(== in order for the first term to be bounded by Note that by our assumptions and by Lemma 18 B(d(v(O), s poly([ R I/g, d, R, m/)
The easiest setting is when > LRie/2 and R = 0 (in this case the value of does not matter); this occurs, for example, if 3 = - Vh for h, and M has positive Ricci curvature. The mixing rate is a = <- Liae and this closely relates to a well known result by Bakry and Emery on the Log- Pog-Sobolev Inequality of CD(,, (c) distributions:
We now discuss few specific cases for Assumption 2.
some c-strongly-conee
32
Theorem ([Bakry al., 2014]) Let Rie denote the Ricci curvature lensor. dr (x) e- --h(w) dvol,( (a)), and 42h + Ric pI, then x² satisfies the Log-Sobolev Inequality (LSI) with parameter
When x" satisfies the LS) it has been shown in [Bakry et al., 2014] that for any initialization, the KL divergence of Law(x(t) of (1.1) with respect to its stationary distribution converges to 0 with rate p. In our example in the preceding paragraph, dx" = =dvovl, satisfies LSI with = c I.Ries which is, up to a constant factor, equal to our mixing rate.
The requirement q + 2 2 is without loss of generality. If q- LRie/2 O, we can take d' = - 2 and verify that B satisfies Assumption 2 with (m, , R). Since q' + LRie/2 = 0, the which corresponds to the easy "C, oo)" setting.
mixing rate is then a = min
m-Lnme/2
16
2R
harder, but more general setting is when 3 1/2 Vh for some non-convex h, and LRie > 0, ie. the manifold can have negative Ricci curvature. We will still need to assume that Vh(z) is contractive for points which are further away than some radius R; otherwise, the SDE (1.1) may drift off to infinity and e may not be integrable. Under Assumption 3, satisfies Assumption 2 with m, g. R. The mixing rate a is then proportional to e -L'' LLe this can be very small if is nonconvex and highly nonsmooth, and the manifold M has large negative Ricci curvature, leading to very slow mixing. This is generally unavoidable, even when M is the flat Euclidean space.
Readers familiar with the Holly Sttly-Stroock perturbation may find the exp ((q + L L /2)R?) term familiar: Let M have diameter and let U have 2q- Lipschitz gradient., so that 3= 2 VU satisfies Assumption 2 with g. Then we decompose U = U1 U2, where Un is - -anae-strongly-conee and U2 is a "perturbation" " with magnitude (2q + RRR. dvod,, satisfies CD,, 20) and thus 22 dvoly has Log- Lobolev constant scaling with exp ((2q + L
Finally, on compact manifolds without boundary, one may take R to be the diameter of the manifold and upper bound the mixing rate by f Lnie/R/
5.1 Proof Sketch of Theorem
The proof of Theorem 1 consists of two steps. The first step is bounding the discretization error of (1.2); we have already done this in Lemma in the previous section.
The second step is showing that two paths of (1.1) converge. To do so, we consider f(d(x(()) v())), where f is Lyapunov function taken from [Eberle, 2016] (its exact form is given in Definition 2 in
8

---

the Appendix). Two key property of f are that (i) 3 exp (-(q+ LRie/ (Rie/22R2//11 - f(r)= S and (ii) (r(r) S 1, so that convergence in ((d(x(()) v(t))) implies convergence in d(x((1). v(t).
Coupling 3 of (t)) and y(t), one can show that f(d(x(t), (t))) contracts with rate a. We quantify the contraction rate in Lemma below. We stress that Lemma 3 is not new; it was first presented by Eberle [2016] (with minor variation), and its proof combines Theorem 6.6.2
Under the
of [Hsu, 2002] with the Lyapunov function analysis of [Eberle, 2016]. For completeness, we provide proof of Lemma 3 in Appendix B.3.
Lemma 3. Assume 3 is (m, R) -distannt dissipative as per Assumption 2, and that is also satisfies As- sumption 3. Further assume that m > LBte/2 and q+ LRie/ /2 2 Let (t)) and y(t) denote solutions to (1.1). Then there exists a Lyapunov function f satisfying 1. f(rr 2 1
2 eexp (-(g (g + D.ue/2YR2 /2)r and 2. [r'(r)) < 1, and a coupling between (t) and y(t), such that for all time T,
E[f(d(x(T), v(T)))] sexp ff( vo)),
where a min m-- Luie /2
exp (- + LRie/2)
2R
Given these two steps, we can now sketch the proof of Theorem 1. Consider an arbitrary step of (1.2). For & E [K6, (k + 1)8), let z(t) denote the solution to (1.1), initialized at z(k)). Then by Lemma 3, (d + 1)6), a((k + 1)5))]] S
On the other hand, by Lemma ([k + 1)6), xx++1) )] S ((83/).. Summing these two bounds, applying triangle
inequality, and using the fact that (r) S 1, we get
(lf(d(((( + 1)6), xx+ S e a6 [If(d(((()),,,))))
(5.1)
Applying the above recursively for k- = K, we get
k of v(0)))] -0))))+ 06) E[f(d(xK, (((])))))((K))))) < -
a
Theorem thus follows from the bounds 1 exp (-(q + Lnie 20uue/2y2///0 12)r S f(r) Sr.
Lastly, we briefly mention a complication in the full proof that we omitted from the above sketch: the discretization error between =((k + 1)6) and #x+11 grows with [](zx)]l. which does not have a global upper bound. In practice, we can verify that d( x²) is sub-Gaussian, so that with high probability d( x²) < Olog (k));; this in turn allows us to bound [|3(,,))] )l via Assumption 3. This is the reason for the dependency on log K and (og(1/0) in the iteration complexity of Theorem 1.
Stochastic Gradient Langevin MCMC
Finally, we bound the iteration complexity of process (2.1), which takes the Euler- Murayama scheme (1.2), and replaces 3(zx) at step k by a stochastic estimate (x(x)))
Theorem 2 (Convergence of SGLD on Riemannian Manifold). Assume the manifold M satisfies Assumptions I and 4. Assume in addition that there exists a constant T' such that for all M, u, v. 2, E T2 M, () (u,0 Assumptions 2 and 3; assume addition that m >> LRie/2 and that R 0.
(u, v) v)w, z) < L' u M|]||=|]| [elllllllll [|||l=|||a|| Let /3 be vector field satisfying
Let y(t) denote the exact geometric SDE given in (1.1). Let xg denote the stochastic Euler Murayama discretization (2.1), where 3y denote independent random vector fields, with [[](x)]] = Bxx) for all x. and [13(z)) - -Bx(x)] S a with probability 1.
Let K Z be some iteration number and 8 be some stepsize. There exists a constant CG poly(L's d, LR. I' log K), such that if < 1. then there is a coupling between I and y (KK)) satisfying the distance bound
T.
Eld(y(Ko), S - -m -mm-mmmmm./ Lm)o (() x0) 20)
Ô hides polynomial dependence on L' d, Ln, L' o. m-LLii/2 log K, log }-
We defer the proof of Theorem 2 to Appendix A.5, where we state the explicit expressions for C,. This is the manifold analog of reflection coupling of Euclidean Brownian motions; [Hsu, 2002, Ch. 6.5]

---

Discussion of Theorem 2
To sample from dx dx)()) = =- = we let ((x) - Vh(a) and let v(0) =x)). The W2 distance between Law(xx) and n² is upper bounded by V [ld((((k), To achieve emoor in W2, Theorem 2 requires () steps. The reasoning is very similar to Theorem 1.
As already discussed in Section the Assumption on Theorem is considerably more restrictive than Theorem 1. We also highlight that the error bound in Theorem 2 does depend on L'p. the derivative of the Riemannain curvature tensor. This is in contrast to Theorem I, where L does not appear in any of the bounds.
Though the iteration complexity for Theorem can be larger than Theorem as it depends additional parameters a and R' (2.1) may nonetheless be faster than (1.2). For example, let h(x) + Ei h,(2)) and assume V/,, Vhyll S for all i, one step of (2.1) can be performed with single gradient computation for a single uniformly sampled h2, whereas (1.2) would require N gradient computations.
Proof Sketch of Theorem and Theoretical Highlights
For any step k let us define M4++1 == exP (63(u(k-)) + V8Cx), where &e ~ Ny (0, I). We v(k6)) (()())))().))))))))))) 165202 On the other hand, once again applying Lemma can verify that ((d(y((k + 1)6), xx+1) S ( By Young's 's inequality and triangle Inequality,
show, Lemma 8, that E[d( 1 I (1 2 (m - Luue/ 2 E(d
E[d(x++1 i. v((k + 1)6)) s (1 (m LRie/
The bound in Theorem follows immediately from applying the above recursively for 1: = 1... K. We note that The contraction in Lemma 8 is in turn derived from Lemma 29, which may be of independent interest as it quantifies the distance evolution between two general discrete-time stochastic processes (which do not have to be diffusions or related to the Gaussian noise).
is elucidative to compare the proof structure of Theorem with that of Theorem above. On a high level, at step k Theorem 1 first approximates the discrete MCMC step (Ix+1) ) by an exact SDE initialized 2y (=((A + 1)6)). It then uses two facts: f (z)()(t) y(t))) contracts under the exact SDE, and 2. the approximation error between 2x+1 and ă (I + 1))) is small. In contrast, at step k, Theorem first approximates the exact SDE (y((k: + 1)6)) by a Fuler-Murayama step (ūk++)) then uses two facts: 1. d( [[(k + 1)6)) contracts under the stochastic Fuler-Murayame step, and the approximation error between 1 and y(kk + 1)8) is small. The reason for this change is to make use of the fact that E[ = 3. conditioned on the randomness up to time kō. Suppose we had followed the proof of Theorem 1 and defined @tt) to be the solution the exact SDE, with drift 3g. then showing contraction of the exact SDE becomes very tricky as B[33k] not equal when conditioned on if) for any > kō.
7 Acknowledgements
Xiang Cheng acknowledge support from NSF BIGDATA grant (1741341) and NSF CCF-2112666 (TILOS AI Research Institute). Jingzhao Zhang acknowledges support by Tsinghua University Initiative Scientific Research Program.
References
P-A Absil and Jérôme Malick. Projection-like retractions on matrix manifolds. SIAM Journal on Optimization, 22(1):135-158, 2012.
P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithms on matrix manifolds.
Princeton University Press, 2009.
Kwangjun Ahn and Sinho Chewi. Efficient constrained sampling via the mirror-langevin algorithm. Advances in Neural Information Processing Systems, 34, 2021.
10

---

Miroslav Bacák. Convex analysis and optimization in Hadamard spaces. de Gruyter, 2014.
Dominique Bakry, Ivan Gentil, Michel Ledoux, et al. Analysis and geometry of Markov diffusson operators, volume 103. Springer, 2014.
Nawaf Bou-Rabee, Andreas Eberle, and Raphael Zimmer. Coupling and convergence for hamiltonian monte carlo. The Annals of applied probability, 30(3):1209-1250, 2020.
Nicolas Boumal. An introduction to optimization on smooth manifolds. To appear with Cambridge University Press, Jan 2022. URL //www htt.:ht:pwww...oollss//////o//// nicolasboommall net/book.
Xiang Cheng, Dong Yin, Peter Bartlett, and Michael Jordan. Stochastic gradient and Langevin processes. In International Conference on Machine Learning, pages 1810-1819. PMLR, 2020.
Sinho Chewi, Thibaut Le Gouic, Chen Lu, Tyler Maunu, Philippe Rigollet, and Austin Stromme. Exponential ergodicity of marror-lnggevn diffusions. Advances in Neural Information Processing Systems, 33: 19573-19988,, 2020.
Alain Durmus and Eric Moulines. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. The Annals of Applied Probability, 27(3): 2017.
Andreas Eberle. Reflection couplings and contraction rates for diffusions. Probability theory and related fields, 166(3))851-88, 2016.
Ramesh Gangolli. On the construction of certain diffusions on a differentiable manifold. Zeitschrift für Wahnscheiinicckeetttheeree und Verwandte Gebiete, 2(5):406-419 1964.
Khashayar Gatmiry and Santosh S Vempala. Convergence of the riemannian langevin algorithm. arXiv preprint arXiv:2204.108/ 2022.
Mark Girolami and Ben Calderhead. Riemann manifold Langevin and Hamiltonian Monte Carlo methods. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 73(2):
123-214, 2011.
Jackson Gorham, Andrew B Duncan, Sebastian Vollmer, Lester Mackey, et al. Measuring sample quality with diffusions. Annals of Applied Probability, 29(5):2884 01128829228,, 2019.
Elton P Hsu. Stochastic analysis on manifolds. Number 38. American Mathematical Soc., 2002.
Erik Jørgensen. The central limit problem for geodesic random walks. Zeitschrift für Wahrschein- lichkeitstheorie und verwandte Gebiete, 32(1):1-64, 1975.
Jürgen Jost. Riemannian geometry and geometric analysis. Springer, seventh edition, 2008.
Hermann Karcher. Riemannian center mass and mollifier smoothing. Communications on pure and applied mathematics, 30(5):509-55) -41199551,111 1977.
John M Lee. Riemannian manifolds: an introduction to curvature, volume 176. Springer Science & Business Media, 2006.
Yin Tat Lee and Santosh S Vempala. Geodesic walks in polytopes. In Proceedings of the 49th Annual ACM SIGACT Symposium theory of Computing, pages 927-940, 2017.
Yin Tat Lee and Santosh S Vempala. Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1 1115-1121, 2018.
Mufan Bill Li and Murat A Erdogdu. Riemannian Langevin algorithm for solving semidefinite
programs. arXiv preprint arXiv:2010.1 176, 2020.
Ruilin Li, Molei Tao, Santosh S Vempala, and Andre Wibisono. The mirror langevin algorithm converges with vanishing bias. In International Conference on Algorithmic Learning Theory, pages 718-742. PMLR, 2022.
Oren Mangoubi and Aaron Smith. Rapid mixing of geodesic walks on manifolds with positive curvature. The Annals of Applied Probability, 28(4):2501-2543, 2018.
Ankur Moitra and Andrej Risteski. Fast convergence for Langevin diffusion with manifold structure. arXiv preprint arXiv:2002.0555
2020.
Michelle Muniz, Matthias Ehrhardt, Michael Günther, and Renate Winkler. Higher strong order methods for Itō SDEs on matrix Lie groups. arXiv preprint arXiv:2102.08 141:23102.04131, 2021.
Sam Patterson and Yee Whye Teh. Stochastic gradient Riemannian Langevin dynamics on the probability simplex. In NIPS, pages 3102-3110, 2013.
Peter Petersen. Riemannian geometry, volume 171. Springer Science & Business Media, 2006.

---

Mare J Piggott and Victor Solo. Geometric Euler-Maruee Maruyama schemes for stochastic differential equations in (n) and SE(n). SIAM Journal on Numerical Analysis, 54(4):2490-251 2016.
Yue Sun, Nicolas Flammarion, and Maryam Fazel. Escaping from saddle points on Riemannian manifolds. arXiv preprint arXiv:1906. 07355, 2019.
Constantin Udriste. Convex functions and optimization methods on Riemannian manifolds, volume 297. Springer Science Business Media, 2013.
Xiao Wang, Qi Lei, and Toannis Panageas. Fast convergence of langevin dynamics manifold: Geodesics meet log-sobolev. Advances in Neural Information Processing Systems, 33:18894 18904, 2020.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamies. In Proceedings of the 28th international conference on machine learning (ICMI-II), pages 681-688. Citeseer, 2011.
Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. In Conference on Learning Theory, pages 1617-1638. PMLR, 2016.
Kelvin Shuangjian Zhang, Gabriel Peyré, Jalal Fadili, and Marcelo Pereyra. Wasserstein control of mirror langevin monte carlo. In Conference on Learning Theory, pages 3814-3841. PMLR, 2020.
12


Reviews:
[{"review_id": "QZCfiPUnVVy", "reviewer": "Reviewer_9bhF", "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. ", "questions": "Minor:\n\n1- Line 28: by $g(x)$ do you mean the Riemannian metric? \n\n2- Line 97: item ii): do you also mean almost surely? \n\n3- What is the Euclidean counterpart of assumption 2? I think including it would make the assumption easier to understand.  \n\n4- 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.  \n\n5- I did not understand the remark following line 276: \"under assumption 3, $\\beta$ satisfies assumption 2\"? Do you mean $q\\leq L'_\\beta$ \n\n6- I think $\\mathcal R$ should not appear in the result of Theorem 2. \n \n\n", "limitations": "Yes", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- Well-written paper given its technical nature\n- Well discussion of related literature and connection to previous results\n- Important and useful theoretical results and their discussion \n- Explicit convergence rate in terms of  constants \n- Generality of the assumptions \n\n\nWeakness: \n- minor clarifications on details \n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7C4LWPiXRSt", "reviewer": "Reviewer_cfEV", "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.", "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?\n- 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)?\n- 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?\n- 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?\n- 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?\n- Are there any simple synthetic examples that satisfy the assumptions?", "limitations": "Some limitations of the analysis are discussed. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\n- 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.\n\n- 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:\n\t1. 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.\n\t2. 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.\n\t3. 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?\n\n- 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.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4GmB2NmLtWr", "reviewer": "Reviewer_QBd7", "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. \n\nGiven 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. ", "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. \n\n# On Lemma 1 - Discretization Error Bound \n\nOn 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. \n\n1. 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? \n\n2. 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? \n\n# On Theorem 1 - Langevin Sampling Bound \n\n1. Can I interpret the assumption of $m - L_{Ric}/2 > 0$ as morally a Bakry--Emery type criterion (especially if $\\mathcal{R}=0$)? \n\n2. 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", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths \n1. 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. \n\n2. 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. \n\n# Weaknesses \n1. 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. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-mtTSty4Hps", "reviewer": "Reviewer_GcMX", "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.", "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? \n\n2. 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. \n\n3. 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 ?\n\n4. 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.\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \nThe appendix seems to be well organized, but it is too long. (I have to say that I cannot read all of the appendix). \n\nThe 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.)\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept