First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces
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.