Extragradient Method with Variance Reduction for Stochastic Variational Inequalities

By Alfredo Noel Iusem, Alejandro Jofré, Roberto Imbuzeiro Oliveira, Philip Thompson. 2017

184 citations recorded by the source corpus.

We propose an extragradient method with stepsizes bounded away from zero for stochastic variational inequalities requiring only pseudomonotonicity. We provide convergence and complexity analysis, a...

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, 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. Simon Lacoste-Julien
2. Gauthier Gidel
3. Peter Richtárik
4. Issam Hadj Laradji
5. Nicolas Loizou
6. Hugo Berard
7. Sharan Vaswani
8. Pascal Vincent

In Computational Mechanics

1. Simon Lacoste-Julien
2. Gauthier Gidel
3. Sharan Vaswani
4. Issam Hadj Laradji
5. Franck Iutzeler
6. Jérôme Malick
7. Peter Richtárik
8. Panayotis Mertikopoulos

In Management Science and Operations Research

1. Simon Lacoste-Julien
2. Gauthier Gidel
3. Issam Hadj Laradji
4. Zhengyuan Zhou
5. Hugo Berard
6. Sharan Vaswani
7. Panayotis Mertikopoulos
8. Shicong Cen

In Optimization & Training

1. Simon Lacoste-Julien
2. Issam Hadj Laradji
3. Gauthier Gidel
4. Peter Richtárik
5. Sharan Vaswani
6. Nicolas Loizou
7. Franck Iutzeler
8. Jérôme Malick

Citations in the corpus

• Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “Moving beyond SGD, in Section 5 we consider the stochastic extra-gradient (SEG) method [24, 31, 36, 41, 55] used to solve general variational inequalities [27].”
• Reducing Noise in GAN Training with Variance Reduced Extragradient (2019, methodology): “Recently, Iusem et al. (2017) proposed an extragradient method with variance reduction for an infinite sum of operators.”
• A Variational Inequality Perspective on Generative Adversarial Networks (2018, background): “Stochastic versions of the extragradient have been recently analyzed (Juditsky et al., 2011; Yousefian et al., 2014; Iusem et al., 2017) for stochastic variational inequalities with bounded constraints .”
• Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling (2020, background): “[10] showed that using increasing batch size can ensure convergence in pseudomonotone variational inequalities.”
• On the convergence of single-call stochastic extra-gradient methods (2019, background): “…techniques are no longer applicable because the contraction property cannot be maintained in the presence of noise; in fact, unless the problem at hand is amenable to variance reduction – e.g., as in [6, 9, 21] – geometric convergence is not possible if the noise process is even weakly isotropic.”
• A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization (2018, background): “The first result in part (i) is well-known, see [41, 31, 39].”
• Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities (2021, methodology): “Convergence measure Merit function (Definition 1) Distance E[k · w⇤k2] Algorithm SEG SOptDE ESA SOptDE [18] (this paper) [19] (this paper) Weak solution exists O(1/✏4) O(1/✏4) — — -weak solution exists — O(1/✏2 log (1)✏ ) O(1/✏) O(1/✏) No.”
• A Variational Inequality Perspective on Generative Adversarial Nets (2018, background): “Stochastic versions of the extragradient have been recently analyzed (Juditsky et al., 2011; Yousefian et al., 2014; Iusem et al., 2017) in the context of stochastic variational inequalities with bounded constraints.”