Stochastic Variance Reduction for Variational Inequality Methods

Abstract

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.

References in corpus (8)

• A Variational Inequality Perspective on Generative Adversarial Networks
• Online Learning with Predictable Sequences
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• Reducing Noise in GAN Training with Variance Reduced Extragradient
• Variance Reduction for Matrix Games
• Global Convergence to the Equilibrium of GANs using Variational Inequalities
• Forward-backward-forward methods with variance reduction for stochastic variational inequalities
• Coordinate Methods for Matrix Games

Cited by in corpus (7)

• Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
• A Unified Analysis of Variational Inequality Methods: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization
• Coordinate Linear Variance Reduction for Generalized Linear Programming
• Method with Batching for Stochastic Finite-Sum Variational Inequalities in Non-Euclidean Setting
• Optimal Analysis of Method with Batching for Monotone Stochastic Finite-Sum Variational Inequalities