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

Abstract

Deciding whether saddle points exist or are approximable for nonconvex-nonconcave problems is usually intractable. We take a step toward understanding a broad class of nonconvex-nonconcave minimax problems that do remain tractable. Specifically, we study minimax problems in geodesic metric spaces. 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, for which we analyze first-order methods for smooth minimax problems.

PDF NeurIPSW OpenReview Semantic Scholar

Cite

Text

Zhang et al. "Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm." NeurIPS 2023 Workshops: OPT, 2023.

Markdown

[Zhang et al. "Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm." NeurIPS 2023 Workshops: OPT, 2023.](https://mlanthology.org/neuripsw/2023/zhang2023neuripsw-sion/)

BibTeX

@inproceedings{zhang2023neuripsw-sion,
  title     = {{Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm}},
  author    = {Zhang, Peiyuan and Zhang, Jingzhao and Sra, Suvrit},
  booktitle = {NeurIPS 2023 Workshops: OPT},
  year      = {2023},
  url       = {https://mlanthology.org/neuripsw/2023/zhang2023neuripsw-sion/}
}