Riemannian Langevin Dynamics: Strong Convergence of Geometric Euler-Maruyama Scheme

This paper establishes the strong convergence with order $1/2$ for a geometric Euler-Maruyama scheme applied to stochastic differential equations on Riemannian manifolds and derives a corresponding Wasserstein bound for sampling via Riemannian Langevin dynamics.

The Gist

Imagine you are trying to teach a robot to walk through a very specific, winding forest. The forest floor isn't flat; it's a complex, curved landscape (a manifold) with hills, valleys, and twists. The robot's goal is to explore this forest randomly but eventually settle down in the most beautiful, peaceful clearing (the target distribution).

This is the problem of Riemannian Langevin Dynamics (RLD). It's a mathematical recipe for how a robot (or a computer algorithm) should wander around a curved surface to find the best spot.

However, computers are bad at walking on curves. They are built to walk on flat, grid-like floors (Euclidean space). To make the robot walk on the curved forest floor, we use a special trick called the Geometric Euler-Maruyama (GEM) scheme. Think of this as a "stepping stone" method: instead of trying to walk the curve perfectly, the robot takes a straight step, then magically teleports back onto the forest floor to the nearest valid spot.

The Big Question

The authors of this paper asked a crucial question: How accurate are these stepping stones?

In the flat world, we know that if you take small steps, your path stays very close to the true path. The error shrinks predictably as you make the steps smaller. But in the curved forest, no one had proven that this "stepping stone" method worked just as well for every single step the robot took. They only knew it worked on average (like saying the robot ends up in the right neighborhood), but not that the robot didn't take a wild, wrong turn at any specific moment.

The Breakthrough

The authors proved that yes, the stepping stone method works perfectly well on curved surfaces too.

They showed that if you take steps of size $h$, the robot's path stays within a distance of roughly $\sqrt{h}$ from the true, perfect path. This is the same level of accuracy we get on flat ground.

How They Did It (The Analogy)

To prove this, the authors used a clever two-step strategy:

1. The "Shadow" Trick (Extrinsic Extension):
   Imagine the forest is a sculpture floating in a giant, empty room. The robot is supposed to stay on the sculpture. The authors realized they could pretend the robot was walking in the empty room (flat space) instead of on the sculpture.

   • They created a "shadow" version of the forest rules that works everywhere in the room, not just on the sculpture.
   • They proved that if the robot walks in the room using standard rules, it stays very close to where it should be if it were walking on the sculpture.

2. The "Snap-Back" Comparison:
   Now they had two paths:

   • Path A: The robot walking on the sculpture (the real, hard way).
   • Path B: The robot walking in the room and being "snapped back" to the sculpture at every step (the easy, computer-friendly way).

   They used a mathematical "ruler" (Taylor expansion) to measure the tiny gap between Path A and Path B. They proved that because the forest (the manifold) doesn't have any weird, infinitely sharp spikes or infinite curves (geometric boundedness), the gap between the two paths is tiny and predictable.

Why This Matters

This isn't just about math theory; it's about Generative AI (like the tools that create images of cats or write stories).

• The Problem: Real-world data (like photos of faces) doesn't live on a flat grid. It lives on a complex, curved shape.
• The Solution: To generate new, realistic data, AI models use these "random walk" algorithms (diffusion models) on that curved shape.
• The Impact: Before this paper, we didn't have a solid guarantee that the computer's "stepping stone" approximation was accurate enough for every single step. Now, we know it is. This gives engineers confidence that they can build faster, more reliable AI models that understand the true, curved structure of data, rather than forcing it into a flat box.

In a Nutshell

The authors took a complex, curved problem that computers struggle with, mapped it onto a flat surface where computers are experts, and proved that the "shortcut" method is just as accurate as the real thing. They closed a gap in our understanding, ensuring that the next generation of AI models can navigate the complex landscapes of real-world data with precision.

Technical Summary

Here is a detailed technical summary of the paper "RLD: Strong Convergence of GEM" by Zhiyuan Zhan and Masashi Sugiyama.

1. Problem Statement

The paper addresses the theoretical gap in the convergence analysis of numerical schemes for Stochastic Differential Equations (SDEs) on Riemannian manifolds, specifically focusing on Riemannian Langevin Dynamics (RLD).

• Context: Diffusion models are increasingly defined on intrinsic data manifolds to capture low-dimensional structures in high-dimensional real-world data. These models rely on RLD, which involves sampling from a target distribution $\mu_\phi \propto e^{-\phi}$ on a manifold $M$.
• The Challenge: While the Geometric Euler–Maruyama (GEM) scheme is the standard discretization method for RLD, its strong (pathwise) convergence rate was not well-established for general manifolds.
  • In Euclidean space, the standard Euler–Maruyama (EM) scheme achieves a strong convergence order of $\gamma = 1/2$.
  • For manifolds, existing results were limited to specific structures (e.g., Lie groups, spheres) or focused on weak convergence (convergence in distribution) and Wasserstein bounds.
  • Open Question: Does the GEM scheme achieve the same strong convergence order of $1/2$ for general embedded Riemannian submanifolds?

2. Methodology

The authors develop a novel extrinsic extension-and-comparison framework to analyze intrinsic manifold-valued SDEs. The core strategy involves bridging the gap between intrinsic geometry and Euclidean analysis.

A. Geometric Setup and Assumptions

The study considers a Riemannian submanifold $M \subset \mathbb{R}^n$. To ensure convergence, the authors impose specific geometric and regularity conditions:

1. Geometric Boundedness (Assumption I): The extrinsic curvature (second fundamental form $\text{II}$) and its covariant derivative ($\nabla \text{II}$) must be uniformly bounded. This ensures local geometric regularity.
2. Global Embedding (Assumption II): $M$ must admit a uniform tubular neighborhood in $\mathbb{R}^n$. This guarantees that the projection map onto $M$ is well-defined and smooth in a neighborhood of $M$.
3. Drift Regularity (Assumption III): The drift vector field $V$ (typically $-\frac{1}{2}\nabla \phi$) must be smooth and bounded (or satisfy sub-linear growth conditions).

B. Technical Framework

The proof proceeds in three main steps:

1. Extrinsic Extension of the SDE:

   • Since the coefficients of the manifold SDE are only defined on $M$, the authors use the Tubular Neighborhood Theorem and Urysohn's Lemma to extend the drift vector field $V$ and the projection operator $P$ to the entire Euclidean space $\mathbb{R}^n$.
   • Crucially, they construct these extensions to be globally Lipschitz continuous. This allows the application of standard Euclidean SDE theory.
   • They define an extended Euclidean SDE: $dX_t = \tilde{U}(X_t)dt + \tilde{P}(X_t)dW_t$, which coincides with the original manifold SDE when $X_t \in M$.

2. Comparison of Discretizations:

   • Extrinsic EM ($Y^h_k$): Apply the standard Euclidean Euler–Maruyama scheme to the extended SDE. Standard theory guarantees $Y^h_k$ converges strongly to the true solution $X_{t_k}$ with order $1/2$.
   • Intrinsic GEM ($X^h_k$): The actual GEM scheme uses the exponential map: $X^h_{k+1} = \exp_{X^h_k}(hV(X^h_k) + \sqrt{h}\xi)$.
   • The Core Comparison: The authors bound the discrepancy $\|X^h_k - Y^h_k\|$. They utilize a Taylor expansion of the exponential map:
     $$\exp_x(v) = x + v + \frac{1}{2}\text{II}_x(v, v) + R_3(x, v)$$
     By analyzing the remainder terms and the geometric structure of the drift correction term $A(x)$ (related to the mean curvature), they show that the one-step error between the intrinsic and extrinsic schemes is controlled by the geometric boundedness of $M$.

3. Triangle Inequality Argument:
   The total error is decomposed as:
   $$\|X^h_k - X_{t_k}\| \leq \|X^h_k - Y^h_k\| + \|Y^h_k - X_{t_k}\|$$
   Both terms are shown to be $O(h^{1/2})$ in the $L^p$ sense.

3. Key Contributions

1. Strong Convergence of GEM: The paper establishes that the Geometric Euler–Maruyama scheme achieves **$p$-strong pathwise convergence of order $1/2$** for Riemannian submanifolds embedded in$\mathbb{R}^n$, matching the classical Euclidean rate.
   • Result: $\mathbb{E}[\max_{0 \leq k \leq N} d_M(X^h_k, X_{t_k})^p] \lesssim h^{p/2}$.
2. General Applicability: Unlike previous works restricted to Lie groups or spheres, this result applies to arbitrary compact Riemannian manifolds (via Nash's embedding theorem) and non-compact manifolds satisfying geometric boundedness (e.g., graphs and level sets).
3. Wasserstein Bounds for Sampling: By combining the strong convergence result with the Bakry–Émery curvature condition, the authors derive a $p$-Wasserstein convergence bound for RLD sampling:
   $$W_p(\mu_\phi, \hat{\mu}_N) \lesssim e^{-\lambda_\kappa T} + h^{1/2}$$
   This quantifies the trade-off between mixing time ($T$) and discretization error ($h$).
4. Technical Innovation: The development of an extrinsic extension framework that allows the use of Euclidean tools (Lipschitz extensions, standard EM analysis) to solve intrinsic manifold problems, while rigorously controlling the error introduced by the extension and the exponential map approximation.

4. Main Results

• Theorem 1 (Strong Convergence): Under Assumptions I, II, and III, the GEM scheme converges strongly with order $1/2$ in the extrinsic Euclidean norm.
• Theorem 2 (Intrinsic Convergence): If the embedding is globally bi-Lipschitz, the convergence holds in the intrinsic Riemannian distance $d_M$.
• Corollary 8 (Compact Manifolds): For any compact Riemannian manifold, the GEM scheme achieves $p$-strong convergence of order $1/2$ regardless of the specific Nash embedding used.
• Theorem 14 (Sampling Bound): For RLD with a potential $\phi$ satisfying the Bakry–Émery condition, the discretized distribution $\hat{\mu}_N$ converges to the target $\mu_\phi$ in $W_p$ distance with a rate dominated by $O(h^{1/2})$ after sufficient mixing time.

5. Significance and Impact

• Theoretical Foundation: This work fills a critical theoretical gap in the analysis of manifold-valued SDEs, providing the first general proof of strong convergence for GEM with the optimal $1/2$ rate.
• Generative Modeling: It provides rigorous justification for using GEM-based diffusion models on data manifolds. Practitioners can now rely on the $O(h^{1/2})$ error bound when designing sampling algorithms for non-Euclidean data (e.g., images on manifolds, directional data, graph-structured data).
• Algorithm Design: The results suggest that for compact manifolds, the choice of embedding does not affect the convergence rate, simplifying the theoretical analysis of manifold learning algorithms.
• Future Directions: The paper identifies limitations, such as the exponential dependence on time $T$ in the constants and the computational difficulty of the exponential map, suggesting future work on retractions and time-dependent constants.

In summary, this paper rigorously validates the Geometric Euler–Maruyama scheme as a robust numerical method for Riemannian Langevin Dynamics, bridging the gap between Euclidean numerical analysis and geometric probability theory.