  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.
