Fast Convergence of Langevin Dynamics on Manifold: Geodesics meet Log-Sobolev

Xiao Wang, Qi Lei, Ioannis Panageas

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.

Heatmap of a probability distribution on a spherical manifold

The Geodesic Langevin Algorithm (GLA)

To ensure samples remain on the manifold, GLA operates using a two-step discretization scheme:

  1. 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).
  2. 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

Abstract

Sampling is a fundamental and arguably very important task with numerous applications in Machine Learning. One approach to sample from a high dimensional distribution $e^{-f}$ for some function $f$ is the Langevin Algorithm (LA). Recently, there has been a lot of progress in showing fast convergence of LA even in cases where $f$ is non-convex, notably \cite{VW19}, \cite{MoritaRisteski} in which the former paper focuses on functions $f$ defined in $\mathbb{R}^n$ and the latter paper focuses on functions with symmetries (like matrix completion type objectives) with manifold structure. Our work generalizes the results of \cite{VW19} where $f$ is defined on a manifold $M$ rather than $\mathbb{R}^n$. From technical point of view, we show that KL decreases in a geometric rate whenever the distribution $e^{-f}$ satisfies a log-Sobolev inequality on $M$.
BibTeX
@inproceedings{wang2020fast,
  author = {Xiao Wang and Qi Lei and Ioannis Panageas},
  title = {{Fast Convergence of Langevin Dynamics on Manifold: Geodesics meet Log-Sobolev}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=GIIHcfXPyS8},
}
Figure