mlsanityData to 7 Oct 2026

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

arXiv 2206.02041 ↗First posted 4 Jun 2022math.OC cs.LG math.DGcited by 10

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 65 of its 148 references that are in the map. First posted on arXiv 4 Jun 2022.

Builds on

65 of 148 references.

References · 65

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2022Generative Adversarial Networkscited by 5,603
  3. 2017How to Escape Saddle Points Efficientlycited by 284
  4. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  5. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  6. 2018Riemannian Adaptive Optimization Methodscited by 187
  7. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  8. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  9. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  10. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
  11. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  12. 2018The Mechanics of n-Player Differentiable Gamescited by 118
38 more
  1. 2013Manopt, a Matlab toolbox for optimization on manifoldscited by 112
  2. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 98
  3. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 97
  4. 2016First-order Methods for Geodesically Convex Optimizationcited by 92
  5. 2017Orthogonal Weight Normalization: Solution to Optimization over Multiple Dependent Stiefel Manifolds in Deep Neural Networkscited by 92
  6. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 75
  7. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
  8. 2018The Unusual Effectiveness of Averaging in GAN Trainingcited by 73
  9. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  10. 2016Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifoldscited by 64
  11. 2016Global rates of convergence for nonconvex optimization on manifoldscited by 61
  12. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 60
  13. 2018Negative Momentum for Improved Game Dynamicscited by 59
  14. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 59
  15. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  16. 2013The Information Geometry of Mirror Descentcited by 53
  17. 2017Metrics for Deep Generative Modelscited by 53
  18. 2015Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picturecited by 49
  19. 2020No-regret learning and mixed Nash equilibria: They do not mixcited by 49
  20. 2018On Gradient-Based Learning in Continuous Gamescited by 46
  21. 2020Projection Robust Wasserstein Distance and Riemannian Optimizationcited by 45
  22. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  23. 2018Averaging Stochastic Gradient Descent on Riemannian Manifoldscited by 39
  24. 2020Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problemscited by 39
  25. 2019A Brief Introduction to Manifold Optimizationcited by 35
  26. 2020Simple and optimal methods for stochastic variational inequalities, I: operator extrapolationcited by 35
  27. 2020On Projection Robust Optimal Transport: Sample Complexity and Model Misspecificationcited by 34
  28. 2018First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problemscited by 33
  29. 2019Escaping from saddle points on Riemannian manifoldscited by 33
  30. 2021On Riemannian Optimization over Positive Definite Matrices with the Bures-Wasserstein Geometrycited by 32
  31. 2019An accelerated inexact proximal point method for solving nonconvex-concave min-max problemscited by 30
  32. 2016Dimensionality Reduction on SPD Manifolds: The Emergence of Geometry-Aware Methodscited by 29
  33. 2019Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Netscited by 29
  34. 2018Local Saddle Point Optimization: A Curvature Exploitation Approachcited by 28
  35. 2019On Lower Iteration Complexity Bounds for the Saddle Point Problemscited by 28
  36. 2019A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimizationcited by 25
  37. 2015Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Methodcited by 24
  38. 2019Efficiently escaping saddle points on manifoldscited by 24

50 most cited of 65 All 65 (JSON)

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 4; 2024: 3; 2025: 2.

10 papers.

  1. 2023Decentralized Riemannian Algorithm for Nonconvex Minimax Problemscited by 7
  2. 2025Riemannian Optimization on Relaxed Indicator Matrix Manifoldcited by 5
  3. 2022Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penaltiescited by 4
  4. 2023Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penaltiescited by 4
  5. 2024A Framework for Bilevel Optimization on Riemannian Manifoldscited by 3
  6. 2023Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computationcited by 2
  7. 2023Extragradient Type Methods for Riemannian Variational Inequality Problemscited by 1
  8. 2024Local convergence of simultaneous min-max algorithms to differential equilibrium on Riemannian manifoldcited by 1
  9. 2024Disciplined Geodesically Convex Programmingcited by 1
  10. 2025Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifoldscited by 1