Revisiting Stochastic Extragradient

Abstract

We fix a fundamental issue in the stochastic extragradient method by providing a new sampling strategy that is motivated by approximating implicit updates. Since the existing stochastic extragradient algorithm, called Mirror-Prox, of (Juditsky et al., 2011) diverges on a simple bilinear problem when the domain is not bounded, we prove guarantees for solving variational inequality that go beyond existing settings. Furthermore, we illustrate numerically that the proposed variant converges faster than many other methods on bilinear saddle-point problems. We also discuss how extragradient can be applied to training Generative Adversarial Networks (GANs) and how it compares to other methods. Our experiments on GANs demonstrate that the introduced approach may make the training faster in terms of data passes, while its higher iteration complexity makes the advantage smaller.

arXiv commentAccepted to AISTATS 2020. 16 pages, 9 figures, 2 algorithms

References in corpus (8)

• Conditional Generative Adversarial Nets
• Self-Attention Generative Adversarial Networks
• NIPS 2016 Tutorial: Generative Adversarial Networks
• A Variational Inequality Perspective on Generative Adversarial Networks
• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• Online Learning with Predictable Sequences
• Reducing Noise in GAN Training with Variance Reduced Extragradient
• A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions

Cited by in corpus (8)

• First Analysis of Local GD on Heterogeneous Data
• Minimax Estimation of Conditional Moment Models
• Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey
• Stochastic Relaxed Inertial Forward-Backward-Forward splitting for Monotone Inclusions in Hilbert spaces
• Tight last-iterate convergence rates for no-regret learning in multi-player games
• A Unified Analysis of Variational Inequality Methods: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Gradient-free algorithm for saddle point problems under overparametrization
• Extrapolation for Large-batch Training in Deep Learning