[ArXiv 2024] Mirror Descent on Riemannian Manifolds: Geometry, Reparameterization, and Convergence

TL;DR

Mirror Descent (MD) is a staple of Euclidean optimization, yet its extension to Riemannian manifolds remained an open challenge. This paper formally introduces Riemannian Mirror Descent (RMD). By viewing MD through the lens of local reparameterization, the authors provide the first non-asymptotic convergence guarantees for manifold-constrained MD and introduce SCGD, a stochastic variant that significantly accelerates optimization on the Stiefel manifold for large-scale applications.

Problem & Motivation: Why wasn't MD on Manifolds "Solved"?

Mirror Descent is traditionally understood through Bregman divergences—geometry-adapted regularizers that handle non-Euclidean constraints (like the probability simplex) gracefully. However, lifting this to a Riemannian Manifold $\mathcal{M}$ is non-trivial:

1. Curvature Obstructions: Unlike the flat Euclidean space, manifolds have curvature. A "global" mirror map $(abla\psi )$ rarely exists or preserves the necessary properties across the entire manifold.
2. Computational Complexity: Standard Riemannian updates often require the Exponential Map, which involves solving a second-order ODE—frequently an intractable task for high-dimensional matrices.

The authors’ core insight is that Mirror Descent is essentially Gradient Descent in a reparameterized coordinate system. By applying this locally, we can sidestep global topological constraints.

Methodology: The RMD Framework

The RMD algorithm (Algorithm 1) replaces the global mirror map with a sequence of local diffeomorphisms ${\varphi }_t$.

The Workflow:

1. Map to Dual: At iteration $t$, map the current point $x_t$ to a dual space $M_t$ via ${\varphi }_t$.
2. Dual Update: Perform a gradient step in the dual space using a retraction (a first-order approximation of the geodesic).
3. Map to Primal: Transform the result back to the manifold using the inverse ${\varphi }_t^{-1}$.

Notation: The framework allows for the recovery of Geodesic Gradient Descent and Euclidean MD as special cases.

Special Case: The Stiefel Manifold & SCGD

For the Stiefel manifold $extSt(n,p)$, the authors use the Cayley Transform as the local reparameterization. To handle large-scale problems where $p$ is large (rendering standard solvers slow), they propose Stochastic Curvilinear Gradient Descent (SCGD). Instead of inverting a full $nimesn$ matrix, SCGD randomly partitions the coordinates into $K$ blocks, creating a block-diagonal skew-symmetric matrix that can be inverted in parallel.

Experiments & SOTA Comparison

The authors validated RMD/SCGD on linear eigenvalue and Orthogonal Procrustes problems.

Key Performance Metric:

On a large-scale Linear Eigenvalue problem ($n=5000$), the stochastic variant (SCGD) demonstrated clear superiority in efficiency:

The results show that SCGD achieves nearly the same precision as deterministic methods but with a ~40% reduction in temporal overhead.

Critical Analysis & Future Outlook

The strength of this work lies in its theoretical rigor—providing $O(1/T^{1/2})$ rates for stochastic nonconvex cases is a significant milestone for manifold optimization.

Limitations:

• Local vs. Global: The reparameterizations are still inherently local. On manifolds with complex topology, the choice of ${\varphi }_t$ might require careful tuning to ensure the "neighborhood" $r$ remains valid.
• Potential for Non-Commuting Parametrization: The paper touches on Hessian manifolds; exploring how global reparameterizations behave under non-commuting structures remains an open question.

Impact: This framework is particularly relevant for Orthonormal Neural Networks and Low-rank Matrix Recovery, where maintaining manifold constraints is critical for stability but traditionally too expensive for SGD-scale training.

Conclusion

"Mirror Descent on Riemannian Manifolds" successfully bridges the gap between the functional flexibility of Mirror Descent and the geometric elegance of Riemannian Optimization. By formalizing the reparameterization intuition, it provides researchers with a robust toolkit for large-scale, geometry-aware machine learning.