We consider a new extension of the extragradient method that is motivated by approximating implicit updates. Since in a recent work chavdarova2019reducing it was shown that the existing stochastic extragradient algorithm (called mirror-prox) of juditsky2011solving diverges on a simple bilinear problem, we prove guarantees for solving variational inequality that are more general than in juditsky2011solving . Furthermore, we illustrate numerically that the proposed variant converges faster than many other methods on the example of chavdarova2019reducing . We also discuss how extragradient can be applied to training Generative Adversarial Networks (GANs). 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. To further accelerate method's convergence on problems such as bilinear minimax, we combine the extragradient step with negative momentum gidel2018negative and discuss the optimal momentum value.
Games generalize the single-objective optimization paradigm by introducing different objective functions for different players. Differentiable games often proceed by simultaneous or alternating gradient updates. In machine learning, games are gaining new importance through formulations like generative adversarial networks (GANs) and actor-critic systems. However, compared to single-objective optimization, game dynamics are more complex and less understood. In this paper, we analyze gradient-based methods with momentum on simple games. We prove that alternating updates are more stable than simultaneous updates. Next, we show both theoretically and empirically that alternating gradient updates with a negative momentum term achieves convergence in a difficult toy adversarial problem, but also on the notoriously difficult to train saturating GANs.