Extragradient Type Methods for Riemannian Variational Inequality Problems
Not on the map. Why?
Abstract (arXiv)
Riemannian convex optimization and minimax optimization have recently drawn considerable attention. Their appeal lies in their capacity to adeptly manage the non-convexity of the objective function as well as constraints inherent in the feasible set in the Euclidean sense. In this work, we delve into monotone Riemannian Variational Inequality Problems (RVIPs), which encompass both Riemannian convex optimization and minimax optimization as particular cases. In the context of Euclidean space, it is established that the last-iterates of both the extragradient (EG) and past extragradient (PEG) methods converge to the solution of monotone variational inequality problems at a rate of Oleft(frac1√Tright) (Cai et al., 2022). However, analogous behavior on Riemannian manifolds remains an open question. To bridge this gap, we introduce the Riemannian extragradient (REG) and Riemannian past extragradient (RPEG) methods. We demonstrate that both exhibit Oleft(frac1√Tright) last-iterate convergence. Additionally, we show that the average-iterate convergence of both REG and RPEG is Oleft(frac1Tright), aligning with observations in the Euclidean case (Mokhtari et al., 2020). These results are enabled by judiciously addressing the holonomy effect so that additional complications in Riemannian cases can be reduced and the Euclidean proof inspired by the performance estimation problem (PEP) technique or the sum-of-squares (SOS) technique can be applied again.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 33 of its 64 references that are in the map. First posted on arXiv 25 Sep 2023.
Builds on
33 of 64 references.
References · 33
- 2017Training GANs with Optimismcited by 217
- 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
- 2016First-order Methods for Geodesically Convex Optimizationcited by 93
- 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
- 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 73
- 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 62
- 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 62
- 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 60
- 2020Differentiating through the Fr'echet Meancited by 53
- 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 49
- 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
- 2015Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methodscited by 37
21 more
- 2018A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivitycited by 36
- 2020Improved Algorithms for Convex-Concave Minimax Optimizationcited by 34
- 2019Escaping from saddle points on Riemannian manifoldscited by 33
- 2022Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalitiescited by 33
- 2015Projected Reflected Gradient Methods for Monotone Variational Inequalitiescited by 27
- 2019A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimizationcited by 25
- 2020From Nesterov's Estimate Sequence to Riemannian Accelerationcited by 24
- 2020Gradient Descent Ascent for Minimax Problems on Riemannian Manifoldscited by 16
- 2020Variational Optimization on Lie Groups, with Examples of Leading (Generalized) Eigenvalue Problemscited by 12
- 2022Riemannian Hamiltonian methods for min-max optimization on manifoldscited by 12
- 2022Momentum Stiefel Optimizer, with Applications to Suitably-Orthogonal Attention, and Optimal Transportcited by 11
- 2022Accelerated Gradient Methods for Geodesically Convex Optimization: Tractable Algorithms and Convergence Analysiscited by 10
- 2022First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spacescited by 10
- 2022Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithmcited by 9
- 2018Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testingcited by 8
- 2021Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equationscited by 8
- 2023Minimizing Dynamic Regret on Geodesic Metric Spacescited by 6
- 2018On Geodesically Convex Formulations for the Brascamp-Lieb Constantcited by 5
- 2023Riemannian Optimistic Algorithmscited by 5
- 2023Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penaltiescited by 4
- 2023Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computationcited by 2
Built on by
Citing papers per year: 2024: 1.
1 paper.