Sion’s Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm
From MaRDI portal
Publication:6060148
extragradientgame theorygeodesic convexitygeodesically complete Riemannian manifoldsminimaxnonconvex-nonconcave problemsRiemannian optimization
Optimality conditions for problems in abstract spaces (49K27) Optimality conditions for minimax problems (49K35) Optimization of shapes other than minimal surfaces (49Q10) Nonconvex programming, global optimization (90C26) Optimality conditions and duality in mathematical programming (90C46) Minimax problems in mathematical programming (90C47)
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.
Recommendations
- Proximal point algorithms for nonconvex-nonconcave minimax optimization problems
- The landscape of the proximal point method for nonconvex-nonconcave minimax optimization
- Alternating Proximal-Gradient Steps for (Stochastic) Nonconvex-Concave Minimax Problems
- Semi-proximal point method for nonsmooth convex-concave minimax optimization
- Projection generalized two-point extragradient quasi-Newton method for saddle-point and other problems
Cites work
- A course in metric geometry
- Accelerated methods for saddle-point problem
- An approach to spectral problems on Riemannian manifolds
- Conic geometric optimization on the manifold of positive definite matrices
- Convergence rate of \(\mathcal{O}(1/k)\) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems
- Convex analysis and optimization in Hadamard spaces
- Elementary proof for Sion's minimax theorem
- Equilibrium points in n -person games
- Equilibrium problems in Hadamard manifolds
- Generalizations of the Nash equilibrium theorem in the KKM theory
- Geometry-aware principal component analysis for symmetric positive definite matrices
- Golden ratio algorithms for variational inequalities
- Greedy adversarial equilibrium: an efficient alternative to nonconvex-nonconcave min-max optimization
- scientific article; zbMATH DE number 52737 (Why is no real title available?)
- scientific article; zbMATH DE number 3479762 (Why is no real title available?)
- scientific article; zbMATH DE number 681023 (Why is no real title available?)
- scientific article; zbMATH DE number 5223994 (Why is no real title available?)
- Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
- Minimax problems on Grassmann manifolds. Sums of eigenvalues
- Nash-type equilibria on Riemannian manifolds: a variational approach
- Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
- On general minimax theorems
- On Helly's theorem in geodesic spaces
- On linear convergence of iterative methods for the variational inequality problem
- Positive Definite Matrices
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Riemannian manifolds are KKM spaces
- Riemannian Stochastic Variance Reduced Gradient Algorithm with Retraction and Vector Transport
- Robust Solutions to Least-Squares Problems with Uncertain Data
- Simple algorithms for optimization on Riemannian manifolds with constraints
- Some additive decompositions of semisimple matrices
- Stochastic saddle-point optimization for the Wasserstein barycenter problem
- The complexity of computing a Nash equilibrium
- The complexity of constrained min-max optimization
- The proximal point algorithm in metric spaces
Cited in
(3)
This page was built for publication: Sion’s Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6060148)
