Revisiting Stochastic Extragradient

By Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin, Peter Richtárik, Yura Malitsky. 2019

83 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Peter Richtárik
2. Nicolas Loizou
3. Simon Lacoste-Julien
4. Ahmed Khaled
5. Gauthier Gidel
6. Ioannis Mitliagkas
7. Konstantin Mishchenko
8. Hugo Berard

In Computer Vision and Pattern Recognition

1. Ioannis Mitliagkas
2. Simon Lacoste-Julien
3. Gauthier Gidel
4. Peter Richtárik
5. Nicolas Loizou
6. Alexia Jolicoeur-Martineau
7. Konstantin Mishchenko
8. Panayotis Mertikopoulos

In Statistical and Nonlinear Physics

1. Gauthier Gidel
2. Simon Lacoste-Julien
3. Ioannis Mitliagkas
4. Nicolas Loizou
5. Peter Richtárik
6. Panayotis Mertikopoulos
7. Franck Iutzeler
8. Jérôme Malick

In Optimization & Training

1. Peter Richtárik
2. Nicolas Loizou
3. Simon Lacoste-Julien
4. Gauthier Gidel
5. Ahmed Khaled
6. Ioannis Mitliagkas
7. Hugo Berard
8. Konstantin Mishchenko

Citations in the corpus

• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, methodology): “Without variance reduction, some work establishes last-iterate convergence results with a slow (sublinear) rate [Rosasco et al., 2014, Mishchenko et al., 2020].”
• Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, background): “It is only very recently that last-iterate convergence guarantees over a non-compact domain appeared in literature for the stochastic problem (Palaniappan & Bach, 2016; Chavdarova et al., 2019; Mishchenko et al., 2020) under the assumption of strong monotonicity.”
• First Analysis of Local GD on Heterogeneous Data (2019, methodology): “Second, there exists at least one method, whose convergence is guaranteed under bounded gradients [6], but in practice the method diverges [3, 12].”
• Tighter Theory for Local SGD on Identical and Heterogeneous Data (2019, methodology): “, 2011), but in practice the method diverges (Chavdarova et al., 2019; Mishchenko et al., 2019).”
• Variance Reduction for Matrix Games (2019, background): “In contrast, only a few works apply variance reduction to finite-sum minimax problems [3, 30, 6, 23], and the potential gains from variance reduction are not well-understood.”
• Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling (2020, background): “[23] for a concurrent series of results, and Ryu et al.”