First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces

Michael I. Jordan, Tianyi Lin, Emmanouil-Vasileios Vlatakis-Gkaragkounis

TL;DR

This paper bridges a major theoretical gap between Euclidean and non-Euclidean optimization. The authors prove that a "corrected" version of the extragradient algorithm can solve min-max problems on Riemannian manifolds with the same optimal linear convergence rates as in flat Euclidean space, debunking previous conjectures that curvature necessitates a significant performance penalty.

What Problem Does This Paper Address?

Min-max optimization is the engine behind many modern machine learning tasks, including Generative Adversarial Networks (GANs), robust dimensionality reduction, and adversarial training. While we have a solid grasp of how these algorithms behave in "flat" Euclidean space, many real-world problems involve constraints that naturally form Riemannian manifolds (like the set of all rotation matrices or positive definite matrices).

The transition from Euclidean to Riemannian geometry is notoriously difficult because of curvature. In flat space, we rely on the law of cosines to track how iterates move toward a solution. On a curved manifold, distances are "distorted," and triangles don't behave nicely.

Triangles on surfaces with positive, zero, and negative curvature

Previous research suggested that this "distance distortion" might cause an unavoidable exponential slowdown when applying standard min-max algorithms to manifolds. This paper asks: Is that performance gap actually necessary?

Methods

The authors focus on two primary algorithms:

  1. Riemannian Corrected Extragradient (RCEG): This is the star of the paper. Standard extragradient methods take a "look-ahead" step to stabilize convergence. RCEG adds a "correction" term in the extrapolation step—specifically using an inverse exponential map—to account for the manifold's nonlinear geometry.
The exponential map projecting a tangent vector onto the manifold
  1. Riemannian Gradient Descent Ascent (RGDA): Analyzed primarily for the stochastic and non-smooth cases.

To prove their results, the authors utilize Trigonometric Comparison Inequalities (TCIs). These are mathematical tools that provide upper and lower bounds on how much a manifold's curvature warps the standard law of cosines, allowing them to bound the "distance distortion" and prove that the algorithm still marches efficiently toward the saddle point.

Datasets

As a theoretical paper, the authors evaluate their algorithms using a synthetic but standard benchmark task:

  • Robust Principal Component Analysis (RPCA): The problem is formulated as a min-max game played over two manifolds: the SPD manifold (Symmetric Positive Definite matrices) and the Sphere manifold ($S^d$).
  • The data consists of sequences of SPD matrices with controlled eigenvalues to test different condition numbers ($\kappa$).

Key Insights and Ideas

  • Closing the Conjectured Gap: The most significant "aha moment" is the proof that RCEG achieves last-iterate linear convergence for geodesically strongly-convex-strongly-concave problems. This matches the best possible rates in Euclidean space, proving that curvature is a quantitative hurdle (affecting constants) rather than a qualitative one (affecting the rate of convergence).
  • Last-Iterate vs. Averaging: Most previous Riemannian proofs only guaranteed convergence for the average of all iterates, which is often slow and rarely used in practice. This paper provides guarantees for the last iterate, which is much more relevant for practitioners.
  • Curvature as a Constant: The complexity bounds do include curvature parameters ($\tau_0, \xi_0$), but these act as multipliers. They don't change the fundamental logarithmic relationship between accuracy ($\epsilon$) and the number of iterations.

Key Results

  • Deterministic Setting: For smooth, strongly-convex-concave problems, RCEG converges at a rate of $O(\kappa \log(1/\epsilon))$, where $\kappa$ is the condition number. This is the "gold standard" for first-order methods.
  • Stochastic Setting: In the presence of noise (common in deep learning), the authors derive near-optimal rates, showing that RCEG is robust to gradient uncertainty even on curved surfaces.
  • Empirical Validation: In RPCA experiments, the "last-iterate" version of RCEG significantly outperformed the "averaged" version, confirming that the theoretical linear convergence translates to faster practical performance.

Limitations and Future Work

  • Tightness of Curvature Constants: While the authors proved the rate is optimal, they acknowledge it is unclear if the specific dependence on the curvature constants ($\tau_0$) is as tight as it could be.
  • Beyond Min-Max: The authors suggest extending this "correction" framework to Riemannian Monotone Variational Inequalities (RMVI), a broader class of problems that includes min-max optimization as a subset.
  • Global vs. Local: The current analysis assumes the manifold has "unique geodesics" (no "holes" or overlaps in the shortest paths between points). Extending these results to more complex, globally non-convex manifolds remains an open challenge.

Summary updated

Abstract

From optimal transport to robust dimensionality reduction, many machine learning applicationscan be cast into the min-max optimization problems over Riemannian manifolds. Though manymin-max algorithms have been analyzed in the Euclidean setting, it has been elusive how theseresults translate to the Riemannian case. Zhang et al. (2022) have recently identified that geodesic convexconcave Riemannian problems admit always Sion’s saddle point solutions. Immediately, an importantquestion that arises is if a performance gap between the Riemannian and the optimal Euclidean spaceconvex concave algorithms is necessary. Our work is the first to answer the question in the negative:We prove that the Riemannian corrected extragradient (RCEG) method achieves last-iterate at alinear convergence rate at the geodesically strongly convex concave case, matching the euclidean one.Our results also extend to the stochastic or non-smooth case where RCEG & Riemanian gradientascent descent (RGDA) achieve respectively near-optimal convergence rates up to factors dependingon curvature of the manifold. Finally, we empirically demonstrate the effectiveness of RCEG insolving robust PCA.
BibTeX
@inproceedings{jordan2022first,
  author = {Michael I. Jordan and Tianyi Lin and Emmanouil-Vasileios Vlatakis-Gkaragkounis},
  title = {{First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=-cfwGiD8cwn},
}
Figure