Extragradient Type Methods for Riemannian Variational Inequality Problems

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

In modern machine learning, Variational Inequality Problems (VIPs) serve as a foundational framework for tasks ranging from constrained convex optimization to the training of Generative Adversarial Networks (GANs). While optimization in Euclidean spaces is well-understood, many contemporary applications—including robotics, computer vision, and Gaussian mixture models—naturally reside on curved Riemannian manifolds. This paper addresses the challenge of extending robust optimization algorithms to these non-Euclidean settings, specifically focusing on "last-iterate" convergence.

The Challenge of Curved Geometry

The transition from flat Euclidean space to curved Riemannian manifolds introduces significant geometric complexities. A primary obstacle is the holonomy effect: when a vector is parallel transported along a closed loop on a curved surface, its final orientation typically differs from its starting orientation.

The holonomy effect: parallel transporting a vector around a geodesic triangle on a sphere results in a geometric shift.

This distortion invalidates standard Euclidean convergence proofs. While previous research established "average-iterate" convergence (where the average of all visited points is optimal), proving that the "last-iterate" (the final point reached) converges has remained a significant hurdle for popular extragradient-style algorithms.

Proposed Riemannian Algorithms

The authors introduce two primary methods adapted for Riemannian manifolds:

  1. Riemannian Extragradient (REG): This algorithm employs a "look-ahead" step to compute a gradient at an intermediate point, then returns to the current iterate to perform a full update based on that information.
  2. Riemannian Past Extragradient (RPEG): An efficient variant that reuses the gradient from the previous iteration for the look-ahead step, effectively halving the per-iteration gradient computations.

The core innovation in their analysis is a novel method for bounding the holonomy effect using geodesic triangles. By quantifying the twisting of vectors within these simple geometric structures, the authors successfully adapted sophisticated Euclidean proof techniques, such as Performance Estimation Problems, to the Riemannian domain.

Theoretical Results and Convergence Rates

The primary contribution of this work is the establishment of the first non-asymptotic last-iterate convergence rates for REG and RPEG in monotone Riemannian VIPs.

Comparison of convergence rates for Riemannian algorithms. REG and RPEG provide the first last-iterate guarantees of $O(1/\sqrt{T})$.

As shown in the table above, both REG and RPEG achieve a last-iterate convergence rate of $O(1/\sqrt{T})$. Furthermore, they maintain the optimal average-iterate convergence rate of $O(1/T)$, matching the best-known results in the field. These rates explicitly incorporate geometric constants ($\zeta$ and $\sigma$) that reflect the manifold's curvature, providing a clear picture of how the space's geometry influences algorithmic performance.

Practical Implications and Future Work

Last-iterate convergence is particularly vital for practical applications like GAN training, where averaging neural network weights often yields nonsensical results. Unlike "doubly-looped" algorithms that require pre-set precision levels, REG and RPEG are "anytime" algorithms that continuously improve as they run.

Future research directions include refining the dependence on curvature constants to achieve tighter bounds, exploring the use of computationally cheaper "retractions" instead of exact exponential maps, and seeking "accelerated" last-iterate rates that might match the $O(1/T)$ performance seen in some Euclidean counterparts.

Summary updated

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