Stochastic Variance Reduction for Variational Inequality Methods
This work addresses optimization challenges in structured min-max problems for researchers and practitioners, representing an incremental advancement by extending variance reduction techniques to variational inequalities.
The paper tackles convex-concave saddle point problems and monotone variational inequalities by proposing stochastic variance reduced algorithms that apply to methods like extragradient and forward-backward-forward, achieving convergence matching or improving best-known complexities, with numerical evaluations on matrix games.
We propose stochastic variance reduced algorithms for solving convex-concave saddle point problems, monotone variational inequalities, and monotone inclusions. Our framework applies to extragradient, forward-backward-forward, and forward-reflected-backward methods both in Euclidean and Bregman setups. All proposed methods converge in the same setting as their deterministic counterparts and they either match or improve the best-known complexities for solving structured min-max problems. Our results reinforce the correspondence between variance reduction in variational inequalities and minimization. We also illustrate the improvements of our approach with numerical evaluations on matrix games.