Abstract
Sampling from high-dimensional distributions is a cornerstone of modern machine learning. While the Langevin Algorithm (LA) is well-understood in Euclidean space, many applications—such as matrix completion, PCA, and GANs—constrain data to curved Riemannian manifolds. We introduce the Geodesic Langevin Algorithm (GLA) and provide the first non-asymptotic convergence guarantees for sampling on manifolds. We demonstrate that if the target distribution satisfies a log-Sobolev inequality, the Kullback-Leibler (KL) divergence decreases at a geometric rate.
Introduction: Beyond Euclidean Space
In many machine learning contexts, we seek to sample from a distribution $e^{-f}$ where $f$ is a potential function. Standard approaches often assume the domain is $\mathbb{R}^n$. However, structural constraints often force data onto manifolds:
- Stiefel Manifolds: Used in PCA and matrix factorization.
- Rank-constrained Matrices: Essential for matrix completion.
- Probability Simplices: Common in game theory and generative modeling.
Applying standard Langevin dynamics to these surfaces is problematic; the "drift" often moves points off the manifold. Previous Riemannian methods either lacked global coordinate independence or rigorous convergence rates. Our work bridges this gap by combining differential geometry with functional analysis.
The Geodesic Langevin Algorithm (GLA)
The GLA discretizes the continuous Riemannian Langevin equation through a two-step iterative process:
- The Tangent Step: At a point $x_k$ on the manifold $M$, we operate in the tangent space $T_{x_k}M$. We calculate the Riemannian gradient $\nabla_M f(x_k)$ and add Gaussian noise. This defines a "proposal" direction in a flat space locally approximating the manifold.
- The Geodesic Step: To return to the manifold, we apply an exponential map $\text{Exp}_{x_k}(\cdot)$, which moves the point along a geodesic (the shortest path on the surface). In practice, we show that computationally cheaper retractions (like orthogonal projections) can substitute for the exponential map without losing convergence guarantees.
Theoretical Results: Log-Sobolev and Geometric Convergence
The primary contribution of this work is proving that the Log-Sobolev Inequality (LSI) is the sufficient condition for fast sampling on manifolds. A distribution $\nu \propto e^{-f}$ satisfies LSI with constant $\alpha$ if for any smooth function $g$: $$\text{Ent}_\nu(g^2) \le \frac{2}{\alpha} \mathbb{E}_\nu [\|\nabla_M g\|^2]$$
We prove that under LSI, the KL divergence $H(p_k|\nu)$ of the GLA iterates $p_k$ converges as: $$H(p_k|\nu) \le e^{-\alpha k \epsilon} H(p_0|\nu) + O(\epsilon)$$ where $\epsilon$ is the step size. This result shows that the algorithm reaches the target distribution exponentially fast, up to a bias term $O(\epsilon)$ caused by discretization. This rate is influenced by the manifold's intrinsic properties, including its Ricci curvature and diameter.
Empirical Validation
To verify our theoretical findings, we tested GLA on synthetic manifolds, most notably the unit sphere $S^{n-1}$. We targeted distributions defined by linear and quadratic potentials to observe how the algorithm populates the surface.
As shown in the figure above, the GLA accurately recovers the "heat map" of the target distribution. Our experiments confirmed that the algorithm reaches steady state within 100,000 iterations and that using simple projections (retractions) yields results indistinguishable from the more complex geodesic paths.
Conclusion and Future Work
We have established a rigorous framework for fast sampling on closed Riemannian manifolds using the Geodesic Langevin Algorithm. By leveraging the Log-Sobolev Inequality, we provide the first non-asymptotic, geometric convergence rates for this class of algorithms.
Future research will look to extend these results to "open" manifolds (e.g., positive definite matrices) and explore Metropolis-Hastings correction steps to eliminate the $O(\epsilon)$ discretization bias, leading to truly unbiased sampling on curved surfaces.
Summary updated