Abstract
This paper establishes a theoretical bridge between discrete stochastic optimization and continuous-time sampling by deriving the "flows" for Riemannian Stochastic Gradient Descent (SGD) and Stochastic Variance Reduced Gradient (SVRG) within the Wasserstein space. By employing the Fokker-Planck equation, the authors develop a unified framework demonstrating that these stochastic methods achieve convergence rates in probability space that align with their well-established Euclidean counterparts.
Introduction
Optimization on Riemannian manifolds—spaces that are locally Euclidean but globally curved—is essential for modern machine learning, particularly in robotics and matrix manifolds. A prominent example is the Wasserstein space, where "points" represent probability distributions. Optimization in this space is intrinsically linked to sampling; for instance, minimizing KL divergence via gradient flow corresponds to Langevin dynamics.
While discrete algorithms like Riemannian SGD and SVRG are well-defined, their continuous-time limits (flows) in Wasserstein space have remained elusive. In Euclidean settings, these limits are described by Stochastic Differential Equations (SDEs), but defining Brownian motion on general manifolds is complex. This research provides the "missing link" between discrete sampling steps and continuous probability evolution.
Methodology: The Fokker-Planck Bridge
The authors circumvent the challenges of manifold-based randomness through a three-step strategy:
- Euclidean Representation: They represent the dynamics of probability measures in Wasserstein space through the dynamics of random vectors in Euclidean space.
- Vanishing Step Size: By taking the limit as the learning rate ($\eta$) approaches zero, discrete Riemannian updates are transformed into a Euclidean SDE.
- Fokker-Planck Translation: The Fokker-Planck (F-P) equation is used to translate the Euclidean SDE into a deterministic partial differential equation (PDE) describing the evolution of probability density over time in Wasserstein space.
This framework defines the Riemannian SGD flow and Riemannian SVRG flow, showing that Stochastic Gradient Langevin Dynamics (SGLD) is the discrete counterpart to the proposed SGD flow.
Key Theoretical Insights
- Deterministic Stochasticity: A core finding is that while underlying particle dynamics are stochastic, the resulting flow in Wasserstein space is a deterministic curve. The randomness of the stochastic gradient is integrated into the evolution of the probability density itself.
- Variance Reduction in SVRG: In the continuous limit, the SVRG flow can eliminate gradient variance in specific cases (e.g., Gaussian targets), degenerating into a standard Gradient Flow with reduced per-step computational complexity.
- Unified Convergence: Convergence criteria (measured by Riemannian gradient norm or KL divergence) match Euclidean rates, suggesting that Wasserstein curvature does not inherently impede these stochastic methods.
Results and Validation
The authors establish rigorous convergence rates for both flows:
- Non-Convex Settings: Riemannian SGD flow achieves $O(1/\sqrt{T})$, while SVRG flow achieves a superior $O(N^{2/3}/T)$, where $N$ is the number of component functions.
- Global Convergence: Under the log-Sobolev inequality, the SGD flow converges at $O(1/T)$, while the SVRG flow achieves exponential convergence ($O(e^{-\gamma T / N^{2/3}})$).
These findings were validated using synthetic environments, including Gaussian targets and Mixtures of Gaussians, confirming that variance reduction provides significant speedups in continuous-time regimes.
Conclusion and Future Work
While this work provides a robust theoretical foundation, it assumes Lipschitz continuity for target log-densities, which may not hold for distributions with heavy tails. Future research could extend this framework to more general Riemannian manifolds and investigate the "discretization gap" to ensure theoretical continuous-time speedups translate effectively to practical discrete sampling software.
Summary updated