Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks

By Tengyuan Liang, James Stokes. 2018

226 citations recorded by the source corpus.

Motivated by the pursuit of a systematic computational and algorithmic understanding of Generative Adversarial Networks (GANs), we present a simple yet unified non-asymptotic local convergence theory for smooth two-player games, which subsumes several discrete-time gradient-based saddle point dynamics. The analysis reveals the surprising nature of the off-diagonal interaction term as both a blessing and a curse. On the one hand, this interaction term explains the origin of the slow-down effect in the convergence of Simultaneous Gradient Ascent (SGA) to stable Nash equilibria. On the other hand, for the unstable equilibria, exponential convergence can be proved thanks to the interaction term, for three modified dynamics which have been proposed to stabilize GAN training: Optimistic Mirror Descent (OMD), Consensus Optimization (CO) and Predictive Method (PM). The analysis uncovers the intimate connections among these stabilizing techniques, and provides detailed characterization on the choice of learning rate.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Generative Models

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

In Statistical and Nonlinear Physics

In Generative Models

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “It is worth mentioning that Lin et al. [2020b] also prove last-iterate convergence of SGDA for different class of problems (they do not assume quasi-strong monotonicity), but the proposed analysis requires much stronger noise conditions.”
A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games (2019, positive): “d OG as perturbations of the proximal point method,Mokhtari et al.(2019) gave new but still separate derivations for the standard linear rates in the bilinear and the strongly convex-concave settings.Liang and Stokes (2019) mentioned the potential impact of the interaction between the players, but t”
Negative Momentum for Improved Game Dynamics (2018, methodology): “Using the same formulation as the one in Mescheder et al. (2017) and Gidel et al.”
ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems and GANs (2019, unknown): “Optimism is a simple modiﬁcation to remedy the cycling behavior of simGD, which can occur even under the bilinear convex-concave setup [8, 9, 10, 36, 17, 28, 42, 50].”
Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems (2020, background): “The EG and OGDA algorithms have additionally received signiﬁcant recent attention due to their ability to improve the training dynamics in GANs (Chavdarova et al. (2019); Gidel et al. (2018a,b); Liang and Stokes (2018); Yadav et al. (2017); Daskalakis et al. (2017)).”
On the convergence of single-call stochastic extra-gradient methods (2019, methodology): “Especially in the context of adversarial networks, there has been a ﬂurry of recent activity relating variants of the Extra-Gradient algorithm to GAN training, see e.g., [9, 14, 18, 19, 24, 28, 44] and references therein.”
Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities (2021, background): “Unfortunately, it is not guaranteed and it can diverge even in simple monotone settings [24].”
Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling (2020, methodology): “We terminate our analysis with a dedicated treatment of aﬃne operators which are commonly studied as a ﬁrst step to understand the training of GANs [1, 6, 9, 17, 23, 39].”
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, background): “This work has focused on attaining improved rates [3, 4,19,21,26,29–31,41,45,48] and/or obtaining last-iterate convergence guarantees [1,2,13–15,20,22,28,35,37,38,43].”
A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach (2019, methodology): “We would like to mention that this result is similar to the one shown in (Liang and Stokes, 2019), except here we analyze OGDA as an approximation of PP.”
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2019, background): “, consensus optimization [32], two-timescale GDA [18], the symplectic gradient [3], the linear-transformed gradient [2], optimistic mirror descent [30, 24], inexact proximal point algorithm [25] and the twotimescale algorithm [29].”
When can Wasserstein GANs minimize Wasserstein Distance? (2020, background): “2 Related works Generative Adversarial Networks The works [29, 16, 25, 9, 10, 13, 21, 28, 22] considers either local convergence property of the GAN training, or the global convergence property when the objective is convex-concave However, there is no clear evidence of how the local property can be ”
A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Differentiable Games (2020, result): “For instance, following Mescheder et al. (2017); Gidel et al.”
Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods (2019, methodology): “This failure was fixed by adding negative momentum or by using primal-dual methods proposed by [22, 21, 8, 13, 15, 33].”
Competitive Gradient Descent (2019, background): “…for existing modiﬁcations of GDA, including those of (Mescheder et al., 2017; Daskalakis et al., 2017; Mertikopoulos et al., 2019) (see also Liang and Stokes (2018)) all require the stepsize to be chosen inversely proportional to an upper bound on σ max ( D 2 xy f ) and indeed we will see…”
On How Well Generative Adversarial Networks Learn Densities: Nonparametric and Parametric Results (2018, background): “…computation of GANs is a considerably harder question (Mescheder, Nowozin, and Geiger, 2017; Daskalakis, Ilyas, Syrgkanis, and Zeng, 2017; Liang and Stokes, 2018; Arbel, Sutherland, Bińkowski, and Gretton, 2018; Lucic, Kurach, Michalski, Gelly, and Bousquet, 2017), which we leave as…”
Local Saddle Point Optimization: A Curvature Exploitation Approach (2018, background): “The work of [24] studied the theory of non-asymptotic convergence to a local Nash equilibrium.”