First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces
This work addresses min-max optimization problems in machine learning applications like optimal transport and robust dimensionality reduction, showing that Riemannian algorithms can match Euclidean ones, which is incremental but important for domain-specific applications.
The paper tackles min-max optimization on Riemannian manifolds by proving that the Riemannian corrected extragradient (RCEG) method achieves linear last-iterate convergence in the geodesically strongly-convex-concave case, matching Euclidean performance, and extends results to stochastic or non-smooth cases with near-optimal rates.
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.