Abstract
From optimal transport to robust dimensionality reduction, a plethora ofmachine learning applications can be cast into the min-max optimizationproblems over Riemannian manifolds. Though many min-max algorithms have beenanalyzed in the Euclidean setting, it has proved elusive to translate theseresults to the Riemannian case. Zhang et al. [2022] have recently shown thatgeodesic convex concave Riemannian problems always admit saddle-pointsolutions. Inspired by this result, we study whether a performance gap betweenRiemannian and optimal Euclidean space convex-concave algorithms is necessary.We answer this question in the negative-we prove that the Riemannian correctedextragradient (RCEG) method achieves last-iterate convergence at a linear ratein the geodesically strongly-convex-concave case, matching the Euclideanresult. Our results also extend to the stochastic or non-smooth case where RCEGand Riemanian gradient ascent descent (RGDA) achieve near-optimal convergencerates up to factors depending on curvature of the manifold.