2018

Global Convergence to the Equilibrium of GANs using Variational Inequalities

Gemp, Ian, Mahadevan, Sridhar

Understand

In optimization, the negative gradient of a function denotes the direction of steepest descent.

Furthermore, traveling in any direction orthogonal to the gradient maintains the value of the function.
In this work, we show that these orthogonal directions that are ignored by gradient descent can be critical in equilibrium problems.
Equilibrium problems have drawn heightened attention in machine learning due to the emergence of the Generative Adversarial Network (GAN).

Built on

On some nonlinear elliptic differential functional equations
P. Hartman and G. Stampacchia · 1966
Earlier work this paper cites.
The extragradient method for finding saddle points and other problems
G. Korpelevich · 1977
Earlier work this paper cites.
Traffic equilibria and variational inequalities
S. Dafermos · 1980
Earlier work this paper cites.
An iterative scheme for variational inequalities
S. Dafermos · 1983
Earlier work this paper cites.
Improving generalization performance using double backpropagation
H. Drucker and Y. Le Cun · 1992
Earlier work this paper cites.
Criteria for differentiable generalized monotone maps
J. P. Crouzeix and J. A. Ferland · 1996
Earlier work this paper cites.
Nonlinear Systems
H. K. Khalil · 1996
Earlier work this paper cites.
Projected Dynamical Systems and Variational Inequalities with Applications
A. Nagurney and D. Zhang · 1996
Earlier work this paper cites.
Generalized monotone nonsmooth maps
S. Schaible and D. Luc · 1996
Earlier work this paper cites.
Natural gradient works efficiently in learning
S. I. Amari · 1998
Earlier work this paper cites.
Generalized set-valued variational inequalities
M. Aslam Noor · 1998
Earlier work this paper cites.
Dynamic noncooperative game theory
T. Basar and G. J. Olsder · 1999
Earlier work this paper cites.
The ode method for convergence of stochastic approximation and reinforcement learning
V. S. Borkar and S. P. Meyn · 2000
Earlier work this paper cites.
Phase space error control for dynamical systems
D. J. Higham, A. R. Humphries, and R. J. Wain · 2000
Earlier work this paper cites.
Nash equilibria, variational inequalities, and dynamical systems
E. Cavazzuti, M. Pappalardo, and M. Passacantando · 2002
Earlier work this paper cites.
Finite-Dimensional Variational Inequalities and Complimentarity Problems
F. Facchinei and Pang J · 2003
Earlier work this paper cites.
Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems
A. Nemirovski · 2004
Earlier work this paper cites.
Stochastic Approximation: A Dynamical Systems Viewpoint
V. Borkar · 2008
Earlier work this paper cites.
No-regret learning in convex games
G. J. Gordon, A. Greenwald, and C. Marks · 2008
Earlier work this paper cites.

Similar

On the convergence of regret minimization dynamics in concave games
E. Even-Dar, Y. Mansour, and U. Nadav · 2009
Cited alongside, same era.
Intrinsic robustness of the price of anarchy
T. Roughgarden · 2009
Cited alongside, same era.
Dynamic optimization and differential games
T. L. Friesz · 2010
Cited alongside, same era.
Convex optimization, game theory, and variational inequality theory
G. Scutari, D. P. Palomar, F. Facchinei, and J. Pang · 2010
Cited alongside, same era.
Solving variational inequalities with stochastic mirror-prox algorithm
A. Juditsky, A. Nemirovski, and C. Tauvel · 2011
Cited alongside, same era.
Np-hardness of deciding convexity of quartic polynomials and related problems
A. A. Ahmadi, A. Olshevsky, P. A. Parrilo, and J. N. Tsitsiklis · 2013
Cited alongside, same era.
On the o(1/t) convergence rate of the projection and contraction methods for variational inequalities with lipschitz continuous monotone operators
X. Cai, G. Gu, and B. He · 2014
Cited alongside, same era.
Generative adversarial nets
I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio · 2014
Cited alongside, same era.
Genga: A generalization of natural gradient ascent with positive and negative convergence results
P. Thomas · 2014
Cited alongside, same era.
Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems
F. Yousefian, A. Nedić, and U. V. Shanbhag · 2014
Cited alongside, same era.
On the convergence properties of non-euclidean extragradient methods for variational inequalities with generalized monotone operators
C. D. Dang and G. Lan · 2015
Cited alongside, same era.
Online monotone optimization
Original
I. Gemp and S. Mahadevan · 2016
Cited alongside, same era.

Then

Wasserstein gan
Original
M. Arjovsky, S. Chintala, and L. Bottou · 2017
Later among the works it cites.
Generalization and equilibrium in generative adversarial nets (gans)
Original
S. Arora, R. Ge, Y. Liang, T. Ma, and Y. Zhang · 2017
Later among the works it cites.
Learning particle physics by example: location-aware generative adversarial networks for physics synthesis
L. de Oliveira, M. Paganini, and B. Nachman · 2017
Later among the works it cites.
Understanding gans: the lqg setting
Original
S. Feizi, C. Suh, F. Xia, and D. Tse · 2017
Later among the works it cites.
Online monotone games
Original
I. Gemp and S. Mahadevan · 2017
Later among the works it cites.
Improved training of wasserstein gans
I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. C. Courville · 2017
Later among the works it cites.
Extragradient method with variance reduction for stochastic variational inequalities
A. N. Iusem, A. Jofré, R. I. Oliveira, and P. Thompson · 2017
Later among the works it cites.
Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants
Original
A. Kannan and U. V. Shanbhag · 2017
Later among the works it cites.
Progressive growing of gans for improved quality, stability, and variation
Original
T. Karras, T. Aila, S. Laine, and J. Lehtinen · 2017
Later among the works it cites.
Least squares generative adversarial networks
X. Mao, Q. Li, H. Xie, R. Y. K. Lau, Z. Wang, and S. P. Smolley · 2017
Later among the works it cites.
The numerics of gans
L. Mescheder, S. Nowozin, and A. Geiger · 2017
Later among the works it cites.
Fisher gan
Y. Mroueh and T. Sercu · 2017
Later among the works it cites.
Mcgan: Mean and covariance feature matching gan
Original
Y. Mroueh, T. Sercu, and V. Goel · 2017
Later among the works it cites.
Gradient descent gan optimization is locally stable
V. Nagarajan and J. Z. Kolter · 2017
Later among the works it cites.
Stabilizing training of generative adversarial networks through regularization
Kevin Roth, Aurelien Lucchi, Sebastian Nowozin, and Thomas Hofmann · 2017
Later among the works it cites.
The mechanics of n-player differentiable games
Original
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel · 2018
Closest in time.
A variational inequality perspective on generative adversarial nets
Original
Gauthier Gidel, Hugo Berard, Pascal Vincent, and Simon Lacoste-Julien · 2018
Closest in time.
Which training methods for gans do actually converge?
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…