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

arXiv: https://arxiv.org/abs/2202.06950 · HTML: https://mlsanity.com/paper/2202.06950/

## Key facts

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

## Builds on (most cited first, 28 of 28)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [First-order Methods for Geodesically Convex Optimization](https://mlsanity.com/paper/1602.06053/) (2016)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds](https://mlsanity.com/paper/1605.07147/) (2016)
- [Averaging Stochastic Gradient Descent on Riemannian Manifolds](https://mlsanity.com/paper/1802.09128/) (2018)
- [Golden Ratio Algorithms for Variational Inequalities](https://mlsanity.com/paper/1803.08832/) (2018)
- [Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2002.09621/) (2020)
- [On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games](https://mlsanity.com/paper/1901.00838/) (2019)
- [Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets](https://mlsanity.com/paper/1912.11940/) (2019)
- [Local Saddle Point Optimization: A Curvature Exploitation Approach](https://mlsanity.com/paper/1805.05751/) (2018)
- [A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization](https://mlsanity.com/paper/1910.10782/) (2019)
- [From Nesterov's Estimate Sequence to Riemannian Acceleration](https://mlsanity.com/paper/2001.08876/) (2020)
- [Gradient Descent Ascent for Minimax Problems on Riemannian Manifolds](https://mlsanity.com/paper/2010.06097/) (2020)
- [Simple algorithms for optimization on Riemannian manifolds with constraints](https://mlsanity.com/paper/1901.10000/) (2019)
- [Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles](https://mlsanity.com/paper/2111.13263/) (2021)
- [Global Riemannian Acceleration in Hyperbolic and Spherical Spaces](https://mlsanity.com/paper/2012.03618/) (2020)
- [Projection Robust Wasserstein Barycenters](https://mlsanity.com/paper/2102.03390/) (2021)
- [Accelerated methods for composite non-bilinear saddle point problem](https://mlsanity.com/paper/1906.03620/) (2019)
- [Stochastic Primal-Dual Method on Riemannian Manifolds with Bounded Sectional Curvature](https://mlsanity.com/paper/1703.08167/) (2017)
- [Stochastic Saddle-Point Optimization for Wasserstein Barycenters](https://mlsanity.com/paper/2006.06763/) (2020)
- [Elements of Convex Geometry in Hadamard Manifolds with Application to Equilibrium Problems](https://mlsanity.com/paper/2107.02223/) (2021)

## Built on by (most cited first, 9 of 9)

- [Riemannian coordinate descent algorithms on matrix manifolds](https://mlsanity.com/paper/2406.02225/) (2024)
- [A Framework for Bilevel Optimization on Riemannian Manifolds](https://mlsanity.com/paper/2402.03883/) (2024)
- [Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method](https://mlsanity.com/paper/2505.12378/) (2025)
- [Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation](https://mlsanity.com/paper/2306.16617/) (2023)
- [A Geometric Unification of Distributionally Robust Covariance Estimators: Shrinking the Spectrum by Inflating the Ambiguity Set](https://mlsanity.com/paper/2405.20124/) (2024)
- [Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds](https://mlsanity.com/paper/2510.21468/) (2025)
- [Extragradient Type Methods for Riemannian Variational Inequality Problems](https://mlsanity.com/paper/2309.14155/) (2023)
- [Local convergence of simultaneous min-max algorithms to differential equilibrium on Riemannian manifold](https://mlsanity.com/paper/2405.13392/) (2024)
- [Riemannian Bilevel Optimization](https://mlsanity.com/paper/2405.15816/) (2024)

## 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.