Abstract
From optimal transport to robust dimensionality reduction, a plethora of machine learning applications can be cast into the min-max optimization problems over Riemannian manifolds. Though many min-max algorithms have been analyzed in the Euclidean setting, it has proved elusive to translate these results to the Riemannian case. Zhang et al. [2022] have recently shown that geodesic convex concave Riemannian problems always admit saddle-point solutions. Inspired by this result, we study whether a performance gap between Riemannian and optimal Euclidean space convex-concave algorithms is necessary. We answer this question in the negative—we prove that the Riemannian corrected extragradient (RCEG) method achieves last-iterate convergence at a linear rate in the geodesically strongly-convex-concave case, matching the Euclidean result. Our results also extend to the stochastic or non-smooth case where RCEG and Riemanian gradient ascent descent (RGDA) achieve near-optimal convergence rates up to factors depending on curvature of the manifold.
The Challenge of Curved Geometry
Min-max optimization—finding a "saddle point" where one player minimizes a function while another maximizes it—is the backbone of modern machine learning applications like Generative Adversarial Networks (GANs), robust dimensionality reduction, and optimal transport.
While these problems are well-understood in flat (Euclidean) spaces, many real-world constraints force variables to live on curved surfaces called Riemannian manifolds (e.g., the set of rotation matrices or positive definite matrices). In these "Geodesic Metric Spaces," the geometry is non-linear. A fundamental challenge is distance distortion: unlike in flat space, the "Law of Cosines" doesn't hold exactly on a manifold.
Previous research suggested this geometric friction might cause an exponential slowdown in convergence rates. This paper asks: Is a performance gap between Riemannian and Euclidean min-max algorithms actually necessary?
Algorithmic Framework
The authors focus on two primary first-order algorithms adapted for the Riemannian setting:
- Riemannian Corrected Extragradient (RCEG): Designed for smooth objectives. It adapts the classical Extragradient method by using "exponential maps" to move along the manifold and "parallel transport" to move gradient information between different points on the surface. The "correction" step is vital for handling the non-linear geometry.
- Riemannian Gradient Descent Ascent (RGDA): Analyzed for non-smooth cases where the objective is Lipschitz but not necessarily differentiable.
The core of their theoretical approach involves Trigonometric Comparison Inequalities (TCIs). By using these inequalities, the authors were able to bound the errors introduced by the manifold's curvature (sectional curvature) and prove that the algorithms still contract toward the saddle point at an optimal rate.
Theoretical Breakthroughs and Results
The paper successfully answers a challenge posed by Zhang et al. (2022), proving that the exponential gap previously feared to exist in Riemannian min-max optimization can be closed.
- Last-Iterate Convergence: Most existing Riemannian proofs only guarantee convergence for the average of all steps taken (ergodic convergence), which is often slow and impractical. This paper proves last-iterate convergence, meaning the very last point the algorithm reaches is guaranteed to be near the solution.
- Curvature as a Quantitative Hurdle: The authors show that while curvature affects the constants in the complexity formula, it does not change the fundamental rate (linear convergence). The geometry makes the problem harder by a fixed factor, not by an order of magnitude.
- Linear Convergence: For geodesically strongly-convex-strongly-concave (GSCSC) problems, RCEG achieves a complexity of $O(\kappa \log(1/\epsilon))$, where $\kappa$ is the condition number. This matches the optimal rate for Euclidean spaces.
- Stochastic Robustness: The authors extend these results to the stochastic setting (SRECG), showing that even with noisy gradient estimates, the algorithm achieves near-optimal convergence rates.
Empirical Validation
As a theoretical optimization paper, the authors evaluate their algorithms using Synthetic Robust Principal Component Analysis (RPCA). They generate sequences of Symmetric Positive Definite (SPD) matrices with controlled eigenvalues. In their RPCA experiments, the "last-iterate" version of RCEG converged significantly faster than the "time-average" version, confirming that their theoretical focus on last-iterate behavior has immediate practical benefits.
Limitations and Future Work
While the rate is linear, the specific dependence on curvature parameters in the bounds might not be perfectly tight. Furthermore, the current theory relies on the problem being geodesically convex-concave. Many deep learning problems (like training GANs) are non-convex-non-concave. Extending these Riemannian guarantees to more general function classes remains a major open frontier. Finally, the authors suggest that RCEG could be further generalized to solve Riemannian Monotone Variational Inequalities (RMVI).
Summary updated