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

2022/02/13 by Peiyuan Zhang, Zhang, Peiyuan, Jingzhao Zhang +3 · 2 citations
Computer Science · Mathematics · #Optimization and Variational Analysis #Advanced Optimization Algorithms Research #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.2202.06950

Abstract

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.

Cited by

• Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds
• On Relatively Smooth Optimization over Riemannian Manifolds

Related

• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces
• A Viscosity Method for the Min-Max Construction of Closed Geodesics
• Minimax Theorems for Possibly Nonconvex Functions
• The proximal point algorithm in metric spaces
• A Riemannian Alternating Descent Ascent Algorithmic Framework for Nonconvex-Linear Minimax Problems on Riemannian Manifolds