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.
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:
- 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.
- 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.
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