Overview
Sampling from high-dimensional probability distributions is a foundational task in machine learning, heavily utilized in Bayesian inference, generative modeling, and finding equilibria in continuous games. A standard approach to sample from a distribution $e^{-f}$ is the Langevin Algorithm. While recent progress has shown fast convergence of the Unadjusted Langevin Algorithm (ULA) in flat Euclidean spaces ($\mathbb{R}^n$), many modern machine learning problems involve variables constrained to curved geometric structures, known as manifolds (e.g., spheres, tori, or spaces of orthogonal matrices).
This paper introduces the Geodesic Langevin Algorithm (GLA) for sampling from complex probability distributions defined on Riemannian manifolds. By leveraging the geometric properties of the manifold and assuming the target distribution satisfies a log-Sobolev inequality, the authors prove that GLA achieves a fast, geometric rate of convergence, extending previous non-asymptotic guarantees from flat spaces to curved spaces.
The Challenge of Manifolds
If you run standard ULA on a manifold, the straight-line updates will immediately push your sample off the curved surface. Existing Riemannian Langevin algorithms often struggle because they rely on global coordinate systems—which do not exist for many manifolds—or they lack rigorous, non-asymptotic proofs of their convergence rates. This work bridges that gap by proposing a globally defined algorithm with mathematically guaranteed fast convergence rates.
The Geodesic Langevin Algorithm (GLA)
To ensure samples remain on the manifold, GLA operates using a two-step discretization scheme:
- Tangent Step: At the current point, the algorithm computes the Riemannian gradient of the target distribution and generates standard Gaussian noise. It combines these to create a velocity vector in the tangent space (a flat plane that perfectly touches the manifold at the current point).
- Geodesic Step: To move to the next point without falling off the manifold, GLA uses the exponential map. This involves solving a second-order ordinary differential equation (ODE) to trace a "geodesic"—the curved-surface equivalent of a straight line—in the direction of the tangent vector.
Unlike standard Riemannian Langevin algorithms that can break down when transitioning between different local coordinate charts, GLA's use of the intrinsic exponential map makes it globally well-defined.
Key Insights and Theoretical Guarantees
The paper provides a purely theoretical framework focused on mathematical proofs of algorithmic convergence, bypassing empirical dataset benchmarking to focus on rigorous bounds.
- Log-Sobolev Inequality (LSI) as the Engine: The key to proving fast (exponential) convergence is the assumption that the target distribution satisfies a log-Sobolev inequality. Because the authors assume a closed (compact) manifold, this LSI condition naturally holds.
- Wasserstein Gradient Flow: The continuous-time Langevin equation on a manifold can be elegantly understood as a gradient flow optimizing the relative entropy in the space of probability measures.
- Bounding the Geometry: The main technical hurdle was bounding discretization errors. When moving from continuous time to discrete steps on a curved surface, errors arise from assuming the gradient is constant in a small neighborhood and approximating the curved manifold with a flat tangent space. The authors successfully bounded these errors using the manifold's curvature and dimension.
Convergence Results
- Geometric Convergence of KL Divergence: The authors prove that the Kullback-Leibler (KL) divergence between the algorithm's current distribution and the target distribution decreases at a rapid, geometric rate.
- Wasserstein Distance Guarantees: Thanks to the Talagrand inequality (implied by the LSI), the algorithm also enjoys a similarly fast convergence rate in the $W_2$ Wasserstein distance.
- Explicit Bias Control: Like ULA in Euclidean space, GLA is a "biased" algorithm. Because it takes discrete steps, it ultimately converges to a distribution slightly different from the exact target. However, the authors provide an explicit upper bound for this bias, which depends on the step size, the manifold's dimension, and its curvature. Practitioners can control this bias by choosing a sufficiently small step size.
Limitations and Future Directions
The theoretical guarantees currently rely on the assumption that the manifold is closed (compact with no boundary). Furthermore, the algorithm requires full access to the manifold's geometric data, such as computing the exponential map via ODE solvers, which can be computationally expensive. Finally, the algorithm remains biased due to discretization.
Promising future directions include generalizing these non-asymptotic convergence results to open manifolds and analyzing unbiased algorithms, perhaps by incorporating a Metropolis-Hastings accept/reject step to correct the discretization bias.
Summary updated