Extragradient Type Methods for Riemannian Variational Inequality Problems

Zihao Hu, Guanghui Wang, Xi Wang, Andre Wibisono, Jacob D. Abernethy, Molei Tao

Abstract

In this work, we consider monotone Riemannian Variational Inequality Problems (RVIPs), which encompass both Riemannian convex optimization and minimax optimization as particular cases. In Euclidean space, 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 $O(1/\sqrt{T})$. However, analogous behavior on Riemannian manifolds remains open. To bridge this gap, we introduce the Riemannian extragradient (REG) and Riemannian past extragradient (RPEG) methods. We demonstrate that both exhibit $O(1/\sqrt{T})$ last-iterate convergence and $O(1/T)$ average-iterate convergence, aligning with observations in the Euclidean case. 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.

Introduction

Many modern machine learning problems—such as training Generative Adversarial Networks (GANs) or performing robust PCA—are framed as Variational Inequality Problems (VIPs). These encompass standard convex optimization but also "games" where two players (minimax) try to optimize against each other. While efficient tools exist for these in flat Euclidean space, many real-world data structures (like rotations, symmetric positive definite matrices, or hyperbolic spaces) are better represented as Riemannian manifolds.

Transitioning from flat space to curved geometry introduces significant challenges. Straight lines are replaced by geodesics, and the "holonomy effect" means that moving a vector around a loop on a manifold (like a sphere) results in a vector that no longer points in its original direction. This "turning" effect breaks standard Euclidean convergence proofs. Until now, it was unknown if popular Extragradient methods could maintain their "last-iterate" convergence—the performance of the final step rather than an average—on these curved surfaces.

Parallel transport and the holonomy effect on a Riemannian manifold.

Riemannian Extragradient Methods

To address these challenges, we introduce two novel algorithms:

  • Riemannian Extragradient (REG): A two-step method that takes a "look-ahead" step, parallel transports the gradient back to the starting point, and then makes a definitive update.
  • Riemannian Past Extragradient (RPEG): A more efficient version that reuses the gradient from the previous iteration to save on computation.

The core innovation lies in bounding the holonomy effect using geodesic triangles. By quantifying exactly how much a vector "twists" when moved along the edges of a triangle on a manifold, we adapted powerful Euclidean proof techniques, such as Performance Estimation Problems (PEP), to the Riemannian setting. Previous attempts relied on mathematically cumbersome "geodesic quadrilaterals"; our work shows that analyzing geodesic triangles is sufficient and significantly simpler for proving last-iterate convergence.

Key Results and Convergence Analysis

Our work provides the first non-asymptotic last-iterate convergence rates for Riemannian extragradient methods. Unlike many previous Riemannian methods that only guaranteed convergence for the average of all steps, REG and RPEG ensure the final iterate converges to the solution. This is critical for applications like GAN training, where the average iterate is often suboptimal.

Comparison of convergence rates for Riemannian extragradient methods.

As shown in the table above, both REG and RPEG achieve a last-iterate convergence rate of $O(1/\sqrt{T})$ for monotone problems and an average-iterate rate of $O(1/T)$. These results explicitly account for the manifold's curvature through constants $\zeta$ and $\sigma$, demonstrating how the geometry of the space influences optimization speed. Furthermore, REG and RPEG are "anytime" algorithms, meaning they are easy to implement and continue to improve the solution without requiring a pre-defined target precision.

Discussion and Future Directions

While this work establishes a robust theoretical foundation, several avenues for future research remain. The required step-sizes in our proofs are relatively small to ensure stability against curvature; finding "tighter" constants could allow for larger, faster steps. Additionally, our focus was on unconstrained problems; extending these last-iterate proofs to manifolds with hard boundaries remains an open challenge. Finally, while we utilize the exponential map and parallel transport, investigating "retractions" (computationally cheaper linear approximations) could further improve the practical efficiency of these methods.

Summary updated

Abstract

In this work, we consider monotone Riemannian Variational Inequality Problems (RVIPs), which encompass both Riemannian convex optimization and minimax optimization as particular cases. In Euclidean space, 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 $O\left(\frac{1}{\sqrt{T}}\right)$ (Cai et al., 2022). However, analogous behavior on Riemannian manifolds remains open. To bridge this gap, we introduce the Riemannian extragradient (REG) and Riemannian past extragradient (RPEG) methods. We demonstrate that both exhibit $O\left(\frac{1}{\sqrt{T}}\right)$ last-iterate convergence and $O\left(\frac{1}{{T}}\right)$ average-iterate convergence, aligning with observations in the Euclidean case. 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.
BibTeX
@inproceedings{hu2024extragradient,
  author = {Zihao Hu and Guanghui Wang and Xi Wang and Andre Wibisono and Jacob D. Abernethy and Molei Tao},
  title = {{Extragradient Type Methods for Riemannian Variational Inequality Problems}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=Gp6j7Slk9D},
}
Figure