We propose stochastic variance reduced algorithms for solving convex-concave saddle point problems, monotone variational inequalities, and monotone inclusions. Our framework applies to extra-gradient, 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.
Funding Agencies|NSF [2023239]; DOE ASCR from Argonne National Laboratory [8F-30039]; European Research Council (ERC) under the European Union [725594]; Wallenberg Al, Autonomous Systems and Software Program (WASP) - Knut and Alice Wallenberg Foundation [305286]