mlsanityData to 7 Oct 2026

Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm

arXiv 2202.06950 ↗First posted 13 Feb 2022math.OC cs.LG stat.MLcited by 9

Not on the map. Why?

Abstract (arXiv)

Deciding whether saddle points exist or are approximable for nonconvex-nonconcave problems is usually intractable. This paper takes a step towards understanding a broad class of nonconvex-nonconcave minimax problems that do remain tractable. Specifically, it studies minimax problems over geodesic metric spaces, which provide a vast generalization of the usual convex-concave saddle point problems. The first main result of the paper is a geodesic metric space version of Sion's minimax theorem; we believe our proof is novel and broadly accessible as it relies on the finite intersection property alone. The second main result is a specialization to geodesically complete Riemannian manifolds: here, we devise and analyze the complexity of first-order methods for smooth minimax problems.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 28 of its 69 references that are in the map. First posted on arXiv 13 Feb 2022.

Builds on

28 of 69 references.

References · 28

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  3. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  4. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  5. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 98
  6. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  7. 2016First-order Methods for Geodesically Convex Optimizationcited by 92
  8. 2020The Complexity of Constrained Min-Max Optimizationcited by 81
  9. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
  10. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 75
  11. 2016Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifoldscited by 64
  12. 2018Averaging Stochastic Gradient Descent on Riemannian Manifoldscited by 39
16 more
  1. 2018Golden Ratio Algorithms for Variational Inequalitiescited by 38
  2. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 37
  3. 2019On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Gamescited by 35
  4. 2019Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Netscited by 29
  5. 2018Local Saddle Point Optimization: A Curvature Exploitation Approachcited by 28
  6. 2019A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimizationcited by 25
  7. 2020From Nesterov's Estimate Sequence to Riemannian Accelerationcited by 24
  8. 2020Gradient Descent Ascent for Minimax Problems on Riemannian Manifoldscited by 16
  9. 2019Simple algorithms for optimization on Riemannian manifolds with constraintscited by 14
  10. 2021Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oraclescited by 12
  11. 2020Global Riemannian Acceleration in Hyperbolic and Spherical Spacescited by 10
  12. 2021Projection Robust Wasserstein Barycenterscited by 8
  13. 2019Accelerated methods for composite non-bilinear saddle point problemcited by 6
  14. 2017Stochastic Primal-Dual Method on Riemannian Manifolds with Bounded Sectional Curvaturecited by 4
  15. 2020Stochastic Saddle-Point Optimization for Wasserstein Barycenterscited by 2
  16. 2021Elements of Convex Geometry in Hadamard Manifolds with Application to Equilibrium Problemscited by 2

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 5; 2025: 2.

9 papers.

  1. 2024Riemannian coordinate descent algorithms on matrix manifoldscited by 4
  2. 2024A Framework for Bilevel Optimization on Riemannian Manifoldscited by 3
  3. 2025Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Methodcited by 3
  4. 2023Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computationcited by 2
  5. 2024A Geometric Unification of Distributionally Robust Covariance Estimators: Shrinking the Spectrum by Inflating the Ambiguity Setcited by 2
  6. 2023Extragradient Type Methods for Riemannian Variational Inequality Problemscited by 1
  7. 2024Local convergence of simultaneous min-max algorithms to differential equilibrium on Riemannian manifoldcited by 1
  8. 2025Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifoldscited by 1
  9. 2024Riemannian Bilevel Optimizationcited by 0