Convergence of Extragradient SVRG for Variational Inequalities: Error Bounds and Increasing Iterate Averaging

Understand

We study the last-iterate convergence of variance reduction methods for extragradient (EG) algorithms for a class of variational inequalities satisfying error-bound conditions.

• Previously, last-iterate linear convergence was only known under strong monotonicity.
• We show that EG algorithms with SVRG-style variance reduction, denoted SVRG-EG, attain last-iterate linear convergence under a general error-bound condition much weaker than strong monotonicity.
• This condition captures a broad class of non-strongly monotone problems, such as bilinear saddle-point problems commonly encountered in two-player zero-sum Nash equilibrium computation.