Extragradient Type Methods for Riemannian Variational Inequality
  Problems
Zihao Hu Guanghui Wang Xi Wang Andre Wibisono Jacob Abernethy Molei Tao
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
$O\left(\frac{1}{\sqrt{T}}\right)$ (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
$O\left(\frac{1}{\sqrt{T}}\right)$ last-iterate convergence. Additionally, we
show that the average-iterate convergence of both REG and RPEG is
$O\left(\frac{1}{{T}}\right)$, 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.