Understanding Over-parameterization in Generative Adversarial Networks
Authors: Yogesh Balaji
Mohammadmahdi Sajedi
Neha Mukund Kalibhat
Mucong Ding
Dominik Stöger
Mahdi Soltanolkotabi
Soheil Feizi
Venue: ICLR 2021 Poster (2021)
Keywords: GAN
Over-parameterization
min-max optimization

Abstract: A broad class of unsupervised deep learning methods such as Generative Adversarial Networks (GANs) involve training of overparameterized models where the number of parameters of the model exceeds a certain threshold. Indeed, most successful GANs used in practice are trained using overparameterized generator and discriminator networks, both in terms of depth and width. A large body of work in supervised learning have shown the importance of model overparameterization in the convergence of the gradient descent (GD) to globally optimal solutions. In contrast, the unsupervised setting and GANs in particular involve non-convex concave mini-max optimization problems that are often trained using Gradient Descent/Ascent (GDA).
The role and benefits of model overparameterization in the convergence of GDA to a global saddle point in non-convex concave problems is far less understood. In this work, we present a comprehensive analysis of the importance of model overparameterization in GANs both theoretically and empirically. We theoretically show that in an overparameterized GAN model with a $1$-layer neural network generator and a linear discriminator, GDA converges to a global saddle point of the underlying non-convex concave min-max problem. To the best of our knowledge, this is the first result for global convergence of GDA in such settings. Our theory is based on a more general result that holds for a broader class of nonlinear generators and discriminators that obey certain assumptions (including deeper generators and random feature discriminators). Our theory utilizes and builds upon a novel connection with the convergence analysis of linear time-varying dynamical systems which may have broader implications for understanding the convergence behavior of GDA for non-convex concave problems involving overparameterized models. We also empirically study the role of model overparameterization in GANs using several large-scale experiments on CIFAR-10 and Celeb-A datasets. Our experiments show that overparameterization improves the quality of generated samples across various model architectures and datasets. Remarkably, we observe that overparameterization leads to faster and more stable convergence behavior of GDA across the board.

Published as a conference paper at ICLR 2021
UNDERSTANDING OVERPARAMETERIZATION IN GENERATIVE ADVERSARIAL NETWORKS
Yogesh Balaji', Mohammadmahdi Sajedi Neha Neha Mukund Kalibhat', MMucnng Ding',
Dominik Stöger", Mahdi Soltanolkotabi', Soheil Feizi'
University of Maryland, College Park, MD
2 University of Southern California, Los Angeles, CA
ABSTRACT
A broad class of unsupervised deep learning methods such Generative Adver- sarial Networks (GANs) involve training of overparameterized models where the number of parameters of the model exceeds certain threshold. Indeed, most suc- cessful GANs used in practice are trained using overparameterized generator and discriminator networks, both in terms of depth and width. A large body of work in supervised learning have shown the importance of model overparameteriiation in the convergence of the gradient descent (GD) to globally optimal solutions. In contrast, the unsupervised setting and GANs in particular involve non-convex concave mini-mat max optimization problems that are often trained using Gradient Descent/Ascent (GDA). The role and benefits of model overparameterization in the convergence of GDA global saddle point in non-convex concave problems is far less understood. In this work, we present comprehensive analysis of the importance of model overparameterization in GANs both theoretically and em- pirically. We thcoretically show that in overparameterized GAN model with 1-layer neural network generator and a linear discriminator, GDA converges to a global saddle point of the underlying non-convex concave min-max problem. To the best of our knowledge, this is the first result for global convergence of GDA such settings. Our theory is based class of nonlinear generators and discriminators that obey certain assumptions (in- cluding deeper generators and random feature discriminators). Our theory utilizes and builds upon novel connection with the convergence analysis of linear time- varying dynamical systems which may have broader implications for understand- ing the convergence behavior of GDA for non-convex concave problems involving overparameterized models. We also empirically study the role of model overpa- rameterization in GANs using several large-scale experiments on CIFAR-10 and Celeb-A datasets. Our experiments show that overparameterization improves the quality of generated samples across various model architectures and datasets. Re- markably, we observe that overparameterization leads to faster and more stable convergence behavior of GDA across the board.
more general result that holds for broader
INTRODUCTION
In recent years, we have witnessed tremendous progress in deep generative modeling with some state-of-the-art models capable of generating photo-realistic images of objects and scenes (Brock al., 2019; Karras et al., 2019; Clark al., 2019). Three prominent classes of deep generative models include GANs (Goodfellow et al., 2014), VAEs (Kingma & Welling, 2014) and normalizing flows (Dinh al., 2017). Of these, GANs remain a popular choice for data synthesis especially the image domain. GANs are based on two player min-max game between generator network that generates samples from a distribution, and a critic (diseriminator) network that discriminates real distribution from the generated one. The networks are optimized using Gradient Descent/Ascent (GDA) to reach a saddle-point of the min-max optimization problem.
First two authors contributed equally. Correspondence yogesh@cs.ummle www.ecccs.mmmdeee edu, sajedi eusc.edu

---

Published as a conference paper at ICLR 2021
Train
173
16
100
32
84
123
021
k=8
102
FID
75
50%
150K.
Hidden Dimension (k)
Training Itoraation
k-128
Figure 1: Overparameterizztion in GANs. We train DCGAN models by varying the size of the hidden dimension k (larger the k, more overparameterized the models are, Fig. 8 for details). Overparameterized GANs enjoy improved training and test FID scores (the left panel), generate high-quality samples (the middle panel) and have fast and stable convergence (the right panel).
One of the key factors that has contributed to the successful training of GANs is model overpa- rameterization, defined based on the model parameters count. By increasing the complexity of discriminator and generator networks, both in depth and width, recent papers show that GANs can achieve photo-realistic image and video synthesis (Brock al., 2019; Clark et al., 2019; Karras et al., 2019). While these works empirically demonstrate some benefits of overparaameterizationn there is lack of a rigorous study explaining this phenomena. In this work, we attempt to provide a comprehensive understanding of the role of overparamettriization in GANs, both theoretically and empirically. We note that while overparameterizattin is a key factor in training successful GANs, other factors such generator and discriminator architectures, regularization functions and model hyperparameters have to be taken into account as well to improve the performance of GANs.
Recently, there has been large body of work in supervised learning (e.g. regression classifica- tion problems) studying the importance of model overparameterization in gradient descent (GD)'s convergence globally optimal solutions (Soltanolkotabi et al., 2018; Allen-Zhu et al., 2019; Du et al., 2019; Oymak & Soltanolkotabi, 2019; Zou & Gu, 2019; Oymak et al., 2019). A key ob- servation in these works is that, under some conditions, overparameterized models experience lazy training (Chizat et al., 2019) where optimal model parameters computed by GD remain close to randomly initialized model. Thus, using linear approximation of the model in the parameter space, one can show the global convergence of GD in such minimization problems.
In contrast, training GANs often involves solving non-convex concave min-max optimization prob- lem that fundamentally differs from a single minimization problem of classffictiio/reersssin The key question is whether overparameterized GANs also experience lazy training in the sense that overparameterized generator and discriminator networks remain sufficiently close to their initializa- tions. This may then lead to a general theory of global convergence of GDA for such overparame- terized non-convex concave min-max problems.
In this paper we first theoretically study the role of overparameterization for a GAN model with a 1-hidden layer generator and linear discriminator. We study two optimization procedures solve this problem: (i) using a conventional training procedure in GANs based on GDA in which gen- erator and discriminator networks perform simultaneous steps of gradient descent optimize their respective models, (ii) using GD to optimize generator's parameters for the optimal discriminator. The latter case corresponds to taking a sufficiently large number of gradient ascent steps update discriminator's 's parameters for each GD step of the generator. In both cases, our results show that in an overparameterized regime, the GAN optimization converges to a global solution. To the best of our knowledge, this is the first result showing the global convergence of GDA in such settings. While in our results we focus on one-hidden layer generators and linear discriminators, our theory is based on analyzing general class of min-max optimization problems which can be used to study much broader class of generators and discriminators potentially including deep generators and deep random caature-basel discriminators. A key component of our analysis is novel connection to ponential stability of non-symmetric time varying dynamical systems in control theory which may have broader implications for theoretical analysis of GAN's training. Ideas from control theory have
2

---

Published as a conference paper at ICLR 2021
also been used for understanding and improving training dynamics of GANs in (Xu et al., 2019; An et al., 2018).
Having analyzed overparameterized GANs for relatively simple models, we next provide compre- hensive empirical study of this problem for practical GANs such as DCGAN (Radford et al., 2016) and ResNet GAN (Gulrajani et al., 2017) trained CIFAR-10 and Celeb-A datasets. For example, the benefit of overparanterization in training DCGANs on CIFAR-10 is illustrated in Figure 1. We have three key observations: (i) the model becomes more overparameterized (e.g. using wider networks), the training FID scores that measure the training error, decrease. This phenomenon has been observed other studies well (Brock al., 2019). (ii) overparameterization does not hurt the test FID scores (i.e. the generalization gap remains small). This improved test-time per- formance can also be seen qualitatively the center panel of Figure 1, where overparameterized models produce samples of improved quality. (iii) Remarkably, overparameterized GANs, with lot of parameters to optimize over, have significantly improved convergence behavior of GDA, both in terms of rate and stability, compared to small GAN models (see the right panel of Figure 1).
In summary, this paper
We provide the first theoretical guarantee of simultaneous GDA's global convergence for an overparameterized GAN with one-hidden neural network generator and a linear discrimi- nator (Theorem 2.1).
By establishing connections with linear vare-ngrying dynamical systems, we provide theoretical framework to analyze simultancous GDA's global convergence for a general overparameterized GAN (including deeper generators and random feature discriminators), under some general conditions (Theorems 2.3 and A.4).
We provide a comprehensive empirical study of the role of model overparameterization in GANs using several large-scale experiments on CIFAR-10 and Celeb-A datasets. We observe overparameterization improves GANs' training error, generalization error, sample qualities as well as the convergence rate and stability of GDA.
THEORETICAL RESULTS
2.1 PROBLEM FORMULATION
Given data points of the form 31, .2, F. E R" the goal of GAN's training is find generator that can mimic sampling from the same distribution as the training data. More specifically, the goal is to find a generator mapping Gz(z) Rd + R" parameterized by E RP, so that Go Go(z1), Go(22), ( Go( with ž 22...., 2, generated i.idd according to N NO, La) has a similar empirical distribution æ1, P2,, .2,...,, Ln To measure the discrepancy between the data points and the GAN outputs, one typically uses a discriminator mapping Dj I - IR parameterized with
Ø E R.. The overall training approach takes the form of the following min-max optimization problem which minimizes the worst-case discrepancy detected by the discriminator
min max
D 1=1
1 Σ Po(Go(z))) R(Ø))
(1)
1=1
Here, R(0) is regularizer that typically ensures the discriminator is Lipschitz. This formulation mimics the popular Wasserstein GAN (Arjovsky al., 2017) (or, IPM GAN) formulations. This optimization problem is typically solved by running Gradient Descent Ascent (GDA) on the mini- mization/maxiiizztion variables.
The generator and discriminator mappings G and D used in practice are often deep neural networks. Thus, the min-max optimization problem above is highly nonlinear and non-convex concave. Sad- dle point optimization is a classical and fundamental problem in game theory (Von Neumann & Morgensterm, 1953) and control (Gutman, 1979). However, most of the classical results apply the
In general, the number of observed and generated samples can be different. However, in practical GAN implementations, batch sizes of observed and generated samples usually the same. Thus, for simplicity, make this assumption in setup.
3

---

Published as a conference paper at ICLR 2021
convex-concave case (Arrow al., 1958) while the saddle point optimization of GANs is often non convex-concave. If GDA converges to the global (local) saddle points, we say it is globally (locally) stable. For general min-max optimization, however, GDA can be trapped in loop even diverge. Except in some special cases (e.g. (Feizi et al., 2018) for a quadratic GAN formulation or (Lei et al., 2019) for the madderpprametrized setup when the generator is one-layer network). GDA is not globally stable for GANs in general (Nagarajan & Kolter, 2017; Mescheder et al., 2018; Adolphs al., 2019; Mescheder al., 2017; Daskalakis al., 2020).
None of these works, however, study the role of model overparameterization in the global/local con- vergence (stability) of GDA. In particular, it has been empirically observed (as we also demonstrate in this paper) that when the generatorrdiisriminaato contain a large number of parameters (i.e. are sufficiently overparameterized) GDA does indeed find (near) globally optimal solutions. In this section we wish to demystify this phenomenon from theoretical perspective.
2.2 DEFINITION OF MODEL OVERPARAMETERIZATII
In this paper, we use overparameterization in the context of model parameters count. Informally speaking, overparameterized models have large number of parameters, that is we assume that the number of model parameters is sufficiently large. In specific problem setups of Section 2, we pre- cisely compute thresholds where the number of model parameters should exceed in order observe nice convergence properties of GDA. Note that the definition of overparameterization based on model parameters count is related, but distinct from the complexity the hypothesis class. For instance, in our empirical studies, when we say we overpurameterize neural network, we fix the number of layers in the neural network and increase the hidden dimensions. Our definition does not include the case where the number of layers also increases, which forms different hypothesis class.
2.3 RESULTS FOR ONE-HIDDEN LAYER GENERATORS AND RANDOM DISCRIMINATORS
In this section, we discuss our main results on the convergence of gradient based algorithms when training GANs in the overparameterized regime. We focus on the case where the generator takes the form of a single hidden-layer ReLU network with d inputs, A hidden units, and m outputs. Specifi- cally, 9 (z) = V ReLU (Wz) 2) with W E Rxd and V E gm denoting the input-to-hidden and hidden-to-output weights. We also consider linear discriminator of the form D(x) d x with an l2 regularizer the weights i.e. R(d) ||d 2/ /2. The overall min-max optimization problem (equation 1) takes the form
|d]le 2
min WE o de R
max
C(W d=
= (d,
Σ (x. VReLU (W x2))) 72 1=1
(2)
Note that we initialize V at random and keep it fixed throughout the training. The common approach solve the above optimization problem to run Gradient Descent Ascent (GDA) algorithm. At iteration I, GDA takes the form
di+1= de + PV (W,, (.,d) d:) W W. - W (W,,
(3)
Next, we establish the global convergence of GDA for overparameteriied model. Note that global saddle point (W*, dd)) is defined as
L(W", d) s L(W" dd) < L(W,d')
for all feasible W and these inequalities hold in a local neighborhood, (W*, d'') is called a local saddle point.
Theorem 2.1 Let T1, .2..... Dr I be n. training data with their mean defined as x "E Dy. Consider the GAN model with linear discriminator of the form D(x) d x parame- terized by d E Rmm and one hidden layer neural network generator of the form G(z) = 6(W 2) parameterized by W E Økxd with V E Raxk a fixed matrix generated at random with i..dd. NO0 at) entries. Also assume the imput data the generator i are generated ii.d. ac- cording NO0 d Ia). Furthermore, assume the generator weights at initialization Wo E R
4

---

Published as a conference paper at ICLR 2021
generated i.i.d. according to o.). Furthermore, assume the standard deviations above obey T. x 2 | / (mdd log d Then, as long as
k =2 C- mat log (d)²
with C a fxxe constant, running GDA updates per equation 3 starting from the random Wu above and do 0 with step-sizes obeying 0 < μ S 1 and 17 fs
with řj S 1, satisfies
324-k
a+
o3
VReLU (W,z.)- - 5 10 1005. "u))"
VReLU (Woz;) -
(4)
This holds with probability at least 1 - (n + 5) e 1500
5k e cn (2k: + 2) zi0
ne - log(d)² where Ct C2 are fixed numerical constants.
To better understand the implications of the above theorem, note that the objective of equation 2 can be simplified by solving the inner maximization in a closed form so that the min-max problem in equation 2 is equivalent to the following single minimization problem:
1 2 7
min L(W) = W
VReLU (Wz,) -
(5)
which has global optimum of zero. As a result equation 4 in Theorem 2.1 guarantees that run- ning simultancous GDA updates achieves the global optimum. This holds as long as the generator network is sufficiently overparameterized in the sense that the number of hidden nodes is polynomi- ally large in its output dimension m and input dimension d. Interestingly, the rate of convergence guaranteed by this result is geometric, guaranteeing fast GDA convergence to the global optima. To the extent of our knowledge, this is the first result that establishes the global convergence of simultaneous GDA for an overparameterized GAN model.
While the result proved above shows the global convergence of GDA for a GAN with 1-hidden layer generator and linear discriminator, for general GAN model, local saddle points may not even exist and GDA may converge to approximate local saddle points (Berard et al., 2020; Farnia & Ozdaglar, 2020). For general min-max problem, (Daskalakis et al., 2020) has recently shown that approximate local saddle points exist under some general conditions on the lipschitzness of the objective function. Understanding GDA dynamics for a general GAN remains an important open problem. Our result in Theorem 2.1 is a first and important step towards that.
We acknowledge that the considered GAN formulation of equation 2 is very simpler than GANs used in practice. Specially, since the discriminator is linear, this GAN can be viewed as a moment- matching GAN et al., 2017) pushing first moments of input and generative distributions towards each other. Alternatively, this GAN formulation can be viewed as one instance of the Sliced Wasser- stein GAN (Deshpande et al., 2018). Although the maximization on discriminator's 'ss parameters is concave, the minimization over the generator's parameters is still non non-convex due to the use of a neural-net generator. Thus, the overall optimization problem a non-trivial non-convex concave min-max problem. From that perspective, our result in Theorem 2.1 partially explains the role of model overparameterizztion in GDA's convergence for GANs.
Given the closed form equation 5, one may wonder what would happen if we run gradient de- scent on this minimization objective directly. That is running gradient descent updates of the form W = W 7/ V (WW-) with L(W) given by equation 5. This is equivalent to GDA but instead of running one gradient ascent iteration for the maximization iteration we run infinitely many. Inter- estingly, in some successful GAN implementations (Gulrajani et al., 2017), often more updates on the discriminator's parameters are run per generator's updates. This is the subject of the next result.
Theorem 2.2 Consider the setup of Theorem 2.1. Then as long as
2 C mdd log (d)
'The zero initialization of d is merely done for simplicity. A similar result can be derived for arbitrary initialization of the discriminator's parameters with minor modifications. See Theorem 2.3 for such result.
5

---

Published as a conference paper at ICLR 2021
107
10'
Disc iors dur
Disc iors dy 10
10"
Finel KSV
10"
10"
107
107
10"1
10"1
10
10"1
1204
236
922
1024
128
236
522
1022
(a) Discriminator trained to optimal- ity
(b) Gradient Descent Ascent
(c) diter steps of discriminator up-
date per generator iteration
Figure 2: Convergence plot a GAN model with linear discriminator and 1-hidden layer generator as the hidden dimension (k) increases. Final mse is the mse loss between true data mean and the mean of generated distribution. over-parameterized models show improved convergence
with C a fixed numerical constant, running GD updates of the form W r+1 1 W, -V/((W,), on the loss given in equation 5 with step-size 1)
2R
with n S. satisfies
VReLU (W,z) - - (1 41 10 77)
VReLU (Wozi) - 2
(6)
1=1
82
This holds with probability at least 1 - (n + 5) ne - log (dj² with C₁, 02 fixed numerical constants.
5k
1n
(2k: + 2)
Afa
This theorem states that if we solve the max part of equation 2 in closed form and run GD on the loss function per equation 5 with enough overparameterization. the loss will decrease a geometric rate to zero. This result holds again when the model is sufficiently overparameterized. The proof of Theorem 2.2 relies framework of supervised learning. Also note that the amount overparameterizzaton required in both Theorems 2.1 and 2.2 is the same.
result from (Oymak & Soltanolkotabi, 2020), which developed in the
2.4 CAN THE ANALYSIS BE EXTENDED TO MORE GENERAL GANS?
In the previous section, we focused on the implications of our results for one-hidden layer generator and linear discriminator. However, as it will become clear in the proofs, our theoretical results based on analyzing the convergence behavior of GDA on a more general min-max problem of the form
|dl
min 1(0, d) = (d) y) @ER'dER"
where f : :R" I. denotes general nonlinear mapping.
Theorem 2.3 (Informal version of Theorem A.4) Consider a general nonlinear mapping f Iº mm with the singular values of its Jacobian mapping around initialization obeying certain assumptions (most notably mmin[ (0o)) 2 a). Then, running GDA iterations of the form
d d: + 4 (ah(
(8)
0 0, 7/ Voh(Or.
with sufficiently small step sizes 1) and obeys
na²
t
(ls(0.) yl1,, S 7
Vl1((0)) E1l ||doll
2
Note that similar to the previous sections one can solve the maximization problem in equation 7 in closed form so that equation is equivalent the following minimization problem
min L(0) = 2 [l y1l?, 0ERP
(9)

---

Published as a conference paper at ICLR 2021
with global optima equal to zero. Theorem 2.3 ensures that GDA converges with fast geometric rate to this global optima. This holds as soon as the model f(0) sufficiently overparameterized which is quantitatively captured via the minimum singular value assumption
the Jacobian at initialization (amin (J (0n) ) 2 a which can only hold when m S p). This general result can thus be used to provide theoretical guarantees for much more general class of generators and discriminators. To be more specific, consider deep GAN model where the generator Ge is deep neural network with parameters and the discriminator is deep random feature model of the form Pa(x) d' (xx) parameterized with d and & R - RM deep neural network with random weights. Then the min- max training optimization problem equation 1 with regularizer R(d) ||]]i, /2 is special instance of equation 7 with
1 Σ (Go(z)) and y: (xx) 72
f(0)
Therefore, the above result in principle be used rigorously analyze global convergence of GDA for an overparameterized GAN problem with a deep generator and a deep random feature discriminator model. However, characterizing the precise amount of overparameterizzttio required for such a result to hold requires a precise analysis of the minimum singular value of the Jacobian of f (0) at initialization well as other singular value related conditions stated in Theorem A.4. We defer such precise analysis to future works.
Numerical Validations: Next, we numerically study the convergence of GAN model considered in Theorems 2.1 and 2.2 where the discriminator is linear network while the generator is one hid- den layer neural net. In our experiments, we gen- erate æ; 's from an m-dimension Gaussian distribu- tion with mean and an identity covariance matrix. The mean vector μ is randomly generated. We train two variants of GAN models using (1) GDA (as con- sidered in Thm 2.1) and (2) GD on generator while solving the discriminator to optimality (as consid- ered in Thm 2.2).
1400
Train FID
1200
Test FID
1000
600
400
200
2018
In Fig. 2, we plot the converged loss values of GAN models trained using both techniques (1) and (2) as the hidden dimension A: of the generator is varied. The MSE loss between the true data mean and the data mean of generated samples is used as eval- uation metric. As this MSE loss approaches 0, the model converges the global saddle point. We ob- serve that overparameterized GAN models show improved convergence behavior than the narrower for larger values of & which shows that with
Hidden dimension
ML. Overparameteriiztioo on MNIST.
Figure
models. Additionally, the MSE loss converges sufficient overparamterization, GDA converges to a global saddle point.
3 EXPERIMENTS
In this section, we demonstrate benefits of overparamterriztion in large GAN models. In particular, we train GANs on two benchmark datasets: CIFAR- (32 x 32 resolution) and Celeb-A (64 x 64 resolution). We use two commonly used GAN architectures: DCGAN and Resnet-based GAN. For both of these architectures, we train several models, each with a different number of filters in each layer, denoted by k. For simplicity, we refer to & as the hidden dimension. Appendix Fig, 8 illustrates the architectures used in our experiments. Networks with large & are more overparameterized.
We use the same value of k for both generator and discriminator networks. This is in line with the design choice made in most recent GAN models (Radford et al., 2016; Brock et al., 2019), where the size of generator and discriminator models roughly maintained the same. We train each model till convergence and evaluate the performance of converged models using FID scores. FID scores measure the Frechet distance between feature distributions of real and generated data

---

Published as a conference paper at ICLR 2021
Train FID
Train
00
Test FID
Test FID
K=
Spore
FID
40
K 128
5632
156
18532
128 Hidden Dimension (k)
238
Hidden Dimeusion (k)
DCGAN, CIFAR
(b) DCGAN, CelebA
(c) DCGAN
50-
Train FID
50
Train FID Test FID
Test FID
k= 16
Scote
4.
60
K= 128
Hidden Dimension
Hidden Dimension
(d) Resnet, CIFAR
(c) Resnet, CelebA
Resnet
Figure 4: Overparamterrzation Results: We plot the FID scores (lower, better) of DCGAN and Resnet DCGAN as the hidden dimension k is varied. Results on CIFAR-10 and Celeb-A are shown on the plots the left and right panels, respectively. Overparameterizzation gives better FID scores.
RID Scoze
64
FID Storre
k 64
200
75
100K Training Iteration
Training Iteation
(a) CIFAR
(b) CelebA
Figure 5: DCGAN Training Results: We plot the FID scores across training iterations of DCGAN on CIFAR- and Celeb-A for different values of hidden dimension k. Remarkably, we observe that over-parameterriztton improves the rate of convergence of GDA and its stability in training.
distributions (Heusel et al., 2017). A small FID score indicates high-quality synthesized samples. Each experiment is conducted for runs, and mean and the variance FID scores are reported.
Overparameterrizttoon yields better generative models: In Fig. 4, we show the plot of FID scores as the hidden dimension (k) varied for DCGAN and Resnet GAN models. We observe clear trend where the FID scores are high (i.e. poor) for small values of k. while they improve as models become more overparameterized. Also, the FID scores saturate beyond and k 128 for Resnet GAN models. Interestingly, these the standard values used in the existing model architecures (Radford et al., 2016; Gulrajani et al., 2017). This trend is also consistent on MLP GANs trained MNIST dataset (Fig. 3). We however notice that FID score in MLP GANs increase marginally as increases from 1024 to 2048. This is potentially due to an increased generalization gap in this regime where it offsets potential benefits of over-vorreee parameterization
for DCGAN models,
Overparameterrzation leads improved convergence of GDA: In Fig. 5, we show the plot of FID scores training iterations for different values for k. We observe that models with larger
8

---

Published as a conference paper at ICLR 2021
18
18
GAN
GAN
Training data memorized
17
Training data memorized
17
16
15
15-
14
13
256
128
Hidden dimension (k)
Hidden dimension (k)
(a) DCGAN
Resnet
Figure 6: Generalization in GANs: We plot the NND scores as the hidden dimension k is varied
for DCGAN (shown (a)) and Resnet (shown (b)) models.
values of converge faster and demonstrate a more stable behavior. This agrees with our theoretical results that overparameterized models have fast rate of convergence.
Generalization gap GANs: To study the generalization gap. we compute the FID scores by using (1) the training-set of real data, which we call FID train, and (2) a held-out validation set of real data, which we call test. Fig. 4, a plot of FID train (in blue) and FID test (in green) are shown the hidden dimension k is varied. We observe that FID test values consistently higher than the the FID train values. Their gap does not increase with increasing overparameterization
However, explained in (Gulrajani et al., 2019), the FID score has the issue of assigning low values to memorized samples. To alleviate the issue, (Gulrajani et al., 2019; Arora et al., 2017) proposed Neural Net Divergence (NND) measure generalization in GANs. In Fig. 6, plot NND scores by varying the hidden dimensions in DCGAN and Resnet GAN trained on CIFAR- 10 dataset. We observe that increasing the value of i decreases the NND score. Interestingly, the NND memorized samples are higher than most of the GAN models. This indicates that overparameterized models have been memorizing training samples and produce better generative models.
of
4 CONCLUSION
In this paper, perform systematic study of the importance of overparameterization in training GANs. We first analyze a GAN model with one-hidden layer generator and a linear discriminator optimized using Gradient Descent Ascent (GDA), Under this setup. we prove that with sufficient overparameterization GDA converges to global saddle point. Additionally, our result demonstrate that overparameterized models have fast rate of convergence. We then validate our theoretical findings through extensive experiments on DCGAN and Resnet models trained on CIFAR- 10 and Celeb-A datasets. We observe overparameterized models to perform well both terms the rate of convergence and the quality of generated samples.
ACKNOWLEDGEMENT
M. Sajedi would like to thank Sarah Dean for introducing (Rugh, 1996). This project was sup- ported in part by NSF CAREER AWARD 1942230, HR001 12090132, HR001 19S0022. NIST 60NANB20D133 and Simons Fellowship on "Foundations of Deep Learning." M. Soltanolkotabi is supported by the Packard Fellowship in Science and Engineering, a Sloan Research Fellowship in Mathematics, NSF-CAREER under award 1846369, the Air Force Office of Scientific Research Young Investigator Program (AFOSR- YIP) under award FA9550-18 1-0078, DARPA Learning with Less Labels (LwLL.) and FastNICS programs, and NSF-CIF awards 1813871 and 2008443.

---

Published as a conference paper at ICLR 2021
REFERENCES
Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmann. Local saddle point optimization: A curvature exploitation approach. In The 22nd International Conference on Arti- ficial Intelligence and Statistics, pp. 486-495, 2019.
Zeyuan Allen-Zhu, Yuanzhi Li. and Zhao Song. convergence theory for deep learning via over- parameterization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML. 2019, Long Beach, California, USA, June 9-15, 2019, volume 97 of Proceedings of Machine Learning Research, pp. 242-252, 2019.
Wangpeng An, Haoqian Wang, Qingyun Sun, Jun Xu, Qionghai Dai, and Lei Zhang. A pid controller approach for stochastic optimization of deep networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8522-8531, 2018.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Proceedings of the 34th International Conference on Machine Learning. ICML 2017, Sydney, Australia, Aug 6-11, 2017, Proceedings of Machine Learning Research, pp. 214-223, 2017.
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (gans). arviv preprint arXiv: 00XXv:/703.00577 2017.
Kenneth Arrow, Leonid Hurwicz, and Hirofumi Uzawa. Studies in linear and non-linear program- ming. Cambridge Univ. Press, 1958.
Hugo Berard, Gauthier Gidel, Amjad Almahairi, Pascal Vincent, and Simon Lacoste- Julien. A closer look at the optimization landscapes of generative adversarial net- works. In International Conference on Learning Representations, 2020. URL attps:///oe httpp:s///peeevveew... net/ http://ewww...ttttooooodddoaaaad htt.:/ommidd-eeeeei.....e
Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale GAN training for high fidelity natural image synthesis. In International Conference on Learning Representations, 2019.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances Neural Information Processing Systems, pp. 2937-2947, 2019.
Aidan Clark, Jeff Donahue, and Karen Simonyan. Adversarial video generation on complex datasets. httpps:/aaaxiv..rr//bb/////// wttp/bo//g///ooooooooo 016771611.......
arXiv preprint arXiv: 2019. URL httpt: //tp:ii:////xv...///a//aap..
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. arXiv preprint arXiv:2009.09623 2020. URL
https://arxiv: wttgg//bb//......ooggg
Ishan Deshpande, Ziyu Zhang, and Alexander G Schwing. Generative modeling using the sliced wasserstein distance. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3483-3491, 2018.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real nvp. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterizee neural networks. In 7th International Conference on Learning Representa- tions, ICLR 2019, New Orleans. LA, USA, May 6-9, 2019, Conference Track Proceedings, 2019.
Farzan Farnia and Asuman Ozdaglar. Gans may have no nash equilibria. 0224 2020.
arXiv preprint
Soheil Feizi, Farzan Farnia, Tony Ginart, and David Tse. Understanding GANs: the LQG setting. arXiv preprint arXiv: 10793, 2018. URL http::/://////////////////m 111..///771119999 793.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Pro- cessing Systems 27, pp. 2672-26800 2014.
10

---

Published as a conference paper at ICLR 2021
Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Im- proved training of wasserstein gans. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp- 5767-5777, 2017.
Ishaan Gulrajani, Colin Raffel, and Luke Metz. Towards GAN benchmarks which require generalization. In International Conference on Learning Representations, 2019. URL
https::/apenreviiee net
Shaul Gutman. Uncertain dynamical systems-a Iyapunov min-max approach. IEEE Transactions on Automatic Control, 24(3):437-443, 1979.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to local nash equilibrium. In Advances in neural information processing systems 30, pp. 6626-6637, 2017.
Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pp. 4401-4410. Computer Vision Foundation / IEEE, 2019.
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference on Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Michel Ledoux. The concentration of measure phenomenon. Number 89 in Mathematical Surveys and Monographs. American Mathematical Soc., 2001.
Qi Lei, Jason D Lee, Alexandros G Dimakis, and Constantinos Daskalakis. learns one-layer networks in wgans. arXiv preprint arXiv:1910.07030, 2019. https://arxix: org/ aww/////.............
Sgd URL
Chun-Liang Li, Wei-Cheng Chang, Yu Cheng, Yiming Yang, and Barnabas Poezos. Mmd gan: To- wards deeper understanding of moment matching network. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, Vishwanathan, and Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 2200-222222222 221002221,,-0 2017.
Lars Mescheder, Sehastian Nowozin, and Andreas Geiger. The numerics of GANs. In Advances in Neural Information Processing Systems 30, pp. 1823-1833, 2017.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. arXiv preprint arXiv:1801.064 2018. URL
Which training methods
for gans do actually converge? https:/ http:///xxivvvvo abss 10188110000 .01.04006..
Vaishnavh Nagarajan and Zico Kolter. Gradient descent GAN optimization is locally stable. In Advances in Neural Information Processing Systems 30, pp. 5591-5600, 2017.
Samet Oymak and Mahdi Soltanolkotabi. Overparameteriized nonlinear learning: Gradient descent takes the shortest path? Proceedings of the 36th International Conference on Machine Learn- ing, ICML 2019, Long Beach, California, USA, June 9-15, 2019, Proceedings of Machine Learn- ing Research, pp. 4951-4960, 2019.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterizaation: global con- vergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 2020.
Samet Oymak, Zalan Fabian, Mingchen Li, and Mahdi Soltamolkotabi. Generalization guaran- tees for neural networks via harnessing the low-rank structure of the jacobian. arXiv preprint 19X,::1906.05392. 2019. URL https:/ aawii.iivvo.... org/ abs 111///96.... 05392.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. In Yoshua Bengio and Yann LeCun (eds.). 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico. May 2-4, 2016, Conference Track Proceedings, 2016.

---

Published as a conference paper at ICLR 2021
Wilson J Rugh. Linear system theory. Prentice-Has Hall,, Inc., 1996.
Mahdi Soltanolkotabi. Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization. IEEE Transactions on Information Theory, 65 (4):2374-2400, 2019.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of peee-parmmtere shallow neural networks. IEEE Transactions on Information Theory, 65(2):742- 2018.
Dave Van Veen, Ajil Jalal, Mahdi Soltanolkotabi, Eric Price, Sriram Vishwanath, and Alexandros G Dimakis. Compressed sensing with deep image prior and learned regularization. arXiv preprint arXiv: 2018. URL https:: htt/iv.ivvvoooo org/ abs/ 1806. 06438.
John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior. Princeton university press, 1953.
Kun Xu, Chongxuan Li, Huanshu Wei, Jun Zhu, and Bo Zhang. Understanding and stabilizing gans' training dynamics with control theory. arXiv preprint arXiv: 13/88 188, 2019.
Difan Zou and Quanquan Gu. An improved analysis of training wer-parametterize deep neural networks. In Advances in Neural Information Processing Systems 32, pp. (055-2064, 2019.
12

---

Published as a conference paper at ICLR 2021
Appendix
A PROOFS
In this section, we prove Theorems 2.1 and 2.2. First, provide some notations we throughout the remainder of the paper in Section A.I. Before proving these specialized results for one hidden layer generators and linear discriminators (Theorems 2.1 and 2.2), we state and prove more general result (formal version of Theorem 2.3) on the convergence of GDA on a general class min-max problems in Section A.3. Then we state a few preliminary calculations in Section A.4. Next, we state some key lemmas in Section A.5 and defer their proofs to Appendix B. Finally, we prove Theorems 2.1 and 2.2 in Sections A.6 and A.7, respectively.
A.1 NOTATION
We will use C, C1. etc. to denote positive absolute constants, whose value may change throughout the paper and from line line. We use Φ (z) ReLU (z) max (0, 2) and its (generalized) derivative ø' (z) (=20) with 1 being the indicator function. a min (X) and T (X) X denote the minimum and maximum singular values of matrix X. For two arbitrary matrices and
B. A & B denotes their kronecker product. The spectral radius of matrix A E C is defined as p (A) max [IA1].-... Aa J. where X; 's are the eigenvalues of A. Throughout the proof we shall
assume ReLU avoid unnecessarily long expressions.
A.2 PROOF SKETCH OF THE MAIN RESULTS
In this section, we provide a brief overview of our proofs. We focus on the main result in this manuscript, which is about the convergence of GDA (Theorem 2.1). To do this study the converge of GDA on the more general min-max problem of the form (see Theorem A.4 for formal statement)
|
min max h(0, d) = (d. (0) y) DER"
(10)
In this case the GDA iterates take the form
d = (1 -1 14) d + μ (0:) y)
(11)
0.+1 = 0: - (0,) d.
Our proof for global convergence of GDA on this min-max loss consists the following steps.
Step 1: Recasting the GDA updates as a linear time-varying system
In the first step we carry series of algebraic manipulations to recast the GDA updates (equa- tion 11) into the following form
T++1 de+1
A,
T d
where r. f y denotes the residuum and A, denotes properly defined transition matrix.
Step Approximation by linear time-invariant system Next, to analyze the behavior of the time-varying dynamical system above we approximate it by the following imee-invriiant linear dynamical system
Fetl d,41
I
II² (0o) (1-p)
T d
II
where Og denotes the initialization. The validity this approximation is ensured by our assumptions on the Jacobian of the function which, among others, guarantee that it does not change too much in a sufficiently large neighborhood around the initialization and that the smallest singular value of J (0p) is bounded from below.
Step 3: Analysis of time-invariant linear dynamical system
To analyze the time-invariant dynamical system above, utilize and refine intricate arguments
13

---

Published as a conference paper at ICLR 2021
from the control theory literature involving the spectral radius of the fixed transition matrix above to obtain
Tr d
- (1-
To
do_
E2
82
Step 4: Completing the proof via a perturbation argument
In the last step of our proof we show that the two sequences
and
will remain close to
de
each other. This is based on novel perturbation argument. The latter combined with Step 3 allows us to conclude
Tt de
na
To
do
which finishes the global convergence of GDA equation 10 and hence the proof of Theorem A.4.
In order to deduce Theorem 2.1 from Theorem A.4, we need to check that the Jacobian at the initialization bounded from below the origin and that it does not change too quickly enough neighborhood. In order to prove that we will leverage recent ideas from the deep learning theory literature revolving around the neural tangent kernel. This allows us to guarantee that this conditions are indeed met, if the neural network is sufficiently wide and the initialization is chosen large enough.
large
The second main result of this manuscript, Theorem 2.2, can be deduced more directly from re- cent results on overparameterized learning (see Oymak & Soltanolkotabi (2020)). Hence, we have deferred its proof to Section A.7.
A.3 ANALYSIS OF GDA: A CONTROL THEORY PERSPECTIVE
In this section we will focus on solving general min- min-max optimization problem of the form
||d|
min max h(0, = (d, (0) y) BER*
(12)
where f _R + R is general nonlinear mapping. In particular, we focus on analyzing the convergence behavior Gradient Descent/Ascent (GDA) on the above loss, starting from initial estimates 0g and dg. In this case the GDA updates take the following form
dr+1 = (1 (1-1)) de + 1 (J (0.) yy)
0.+1 = 0: -0.11-0--11 J (0:) d,
(13)
We note that solving the inner maximization problem in equation 12 would yield
min EE
/I (0) - -y1
(14)
In this section, our goal is to show that when rumning the GDA updates of equation 13, the norm of the residual vector defined as := (0.) goes to zero and hence we reach global optimum of equation 14 (and turn equation 12).
Our proof will build on ideas from control theory and dynamical systems literature. For that, we are first going to rewrite the equations 13 in more convenient way. We define the average Jacobian along the path connecting two points æ. E R8" as
S J (xc (xx x)) da,
J (g.x)
where (8) E m is the Jacobian associated with the nonlinear mapping f. Next, from the fundamental theorem of calculus follows that
T++1 = (0++1) - y = (0. - nT. di) y
=f IItt1 J.. de =r: nJtt1 di.
(15)
14

---

Published as a conference paper at ICLR 2021
where we used the shorthands Ji J (0t) and Ji-1,e J (0(+1, for exposition purposes.
Next, we combine the updates r; and d, into state vector of the form =
2m. Using
d,
this notation the relationship between the state vectors from one iteration to the next takes the form
J..LIJ (1-P) p)
2++1
1u
2t. t t20 0,
(16)
which resembles time-varying linear dynamical system with transition matrix A, Now note that to show convergence of F, to zero it suffices to show convergence of 23 to zero. To do this we utilize the following notion of uniform exponential stability, which will crucial in analyzing the solutions of equation 16. (See Rugh (1996) for comprehensive overview on stability notions in discrete state equations.)
Definition 1 A linear state equation of the form 2t-1 Az is called uniformly exponentially stable if for every t 2 0 we have ||zelle, I >X' Izollez where y 2 is a finite constant and O 1.
Using the above definition to show the convergence of the state vector zero at geometric rate suffices to show state equation 16 is exponentially stable. For that, we are first going to analyze state equation which results from linearizing the nonlinear function (0) around the initialization Og. In the next step, we are going to show that the behavior these two problems are similar, provided we stay close initialization (which we also going to prove). Specifically, consider the linearized problem
min max hin (0.d) := (d. (0u) To - 00) 3)
(17)
@ERndER"
We first analyze GDA on this lincarized problem starting from the same initialization the original problem, i.e. 0g Og and do do. The gradient descent update for O, takes the form
0-11 = 0, Jo de,
(18)
and the gradient ascent update for d, takes the form
det d; 11 (Oo) + To (0, - 00) -y -d.)
(19)
= = (1 - u1) d, + pr:
where used the linear residual defined as F. f (0.)+ + Tu 00, (8)- y. Moreover, the residual from one iterate to the next can be written as follows
Fet1 f (00) + To ( 00 y
(00) + To 0 To dj 0o)
(20)
F, -nJooo de
Again, we define new vector 2,
E R22m and by putting together equations 19 and 20 we
d
arrive at
To p)
E =
2 AZ,, 1 12 0,
(21)
nI
(1
We that technically the dynamical system equation 16 is not linear. However, we still exponential stability with some abuse of notation to refer to the property that || S 7'x || holds. As we will see in the forth-coming paragraphs, our formal analysis is via novel perturbation analysis of linear dynamical system and therefore keeping this terminoloyy is justified.
15

---

Published as a conference paper at ICLR 2021
which is of the form of a linear time-invariant state equation. As first step in proof, going to show that the linearized state equations are uniformly exponentially stable. First, recall the following well-knoww lemma, which characterizes uniform exponential stability in terms of the eigenvalues of A.
Lemma A. (Rugh, 1996, Theorem 22.11) linear state equation of the form E④41 Až with A fixed matrix is uniformly exponentially stable if and only if all eigenvalues of A have magnitudes strictly less than one, Lee. (A) <1 In this case, it holds for all 2 and all z that
|| A 21 S 7P (A) |||||,
where y 2 1 an absolute constant, which only depends on A.
In the next lemma, prove that under suitable assumptions To and the step sizes μ and nj the state equations 21 indeed fulfill this condition.
Lemma A.2 Assume that a mmn (Jo) S Omax (Tu) S B and consider the matrix A I auT
Suppose that t. " 2 4B2 Then it holds that (A) S na?
Proof Suppose that À is an eigenvalue of A. Hence, there is an eigenvector [x, y 7 * 0 such that
JnJo |u (1 p1)
ac
= A
y
y
holds. By direct calculation we observe that this yields the equation
(-
MJoo
+ +(1 +(1- x.
1
In particular, must be an eigenvector of InJoo obtain the identity
Denoting the corresponding eigenvalue with 8, we
A)2
-1 ns =
Hence, we must have
1 +
2 sam
11
112
x
pms
Note that the square root is indeed well-defined, since
n 1n pms
pmss 2 0,
where in the first inequality we used the assumption > 4 and in the second line we used that S ,32, which is consequence of our assumption on the singular values of To. Hence, it follows by the reverse triangle inequality that
| - -1- (
(1-
m - pas < 1r 1- (())
2 < 1 2 naa
where the second inequality valid as " 17s 0 is implied by 2 2n ns.. the last inequality we used the fact that a² S 8, which is a consequence of our assumption on the singular values of To. By rearranging terms, obtain that |\| < ? Since À was arbitrary eigenvalue of A, the result follows.
Since the last lemma shows that under suitable conditions it holds that p (A) < 1, Lemma A.3 yields uniform exponential stability of our state equations. However, this will not be sufficient for purposes. The reason is that Lemma A.3 does not specify the constant y and that in order to deal with the üime-varying dynamical system we will need a precise estimate. The next lemma shows that for the state equations 21 we have, under suitable assumptions, 7 5.
16

---

Published as a conference paper at ICLR 2021
Lemma A.3 Consider the linear, time invariant system of equations
I -nJoJ
2++1 jul (1- uJ (1-M)1
2 AZ t t 0.
Furthermore, assume that S miin (Jo) S max (Jo) S 3 and suppose that the condition &. 2 833 satisfied. Then there a constant y S such that for all t 2 it holds that
Erlle <> (nn) 1|
Proof Denote the SVD decomposition of To by WEVT and note that
-JJoo
W 0 I
-E
Wr
0
1ul (1 (1-14 11
W
(1
- 11)
0 W
This means we can write
0
Ci
uI (1-
I -JJJ 11)
W
0
W
0
P
pr
WT
0
W
0
O
Cm
-1j0
where P permutation matrix and the matrices C, are of the form C,
for
(1- μ)
(1
1 S i S m, where the a;'s 's denote the singular values of To. Using this decomposition we can deduce
c Elle = || 20 lle, <
=
max Isism
Now suppose that V,D,V, is the eigenvalue decomposition of C, where the columns of V; contain the eigenvectors and D: is a diagonal matrix consisting of the eigenvalues. (Note that it follows from our assumptions on and r that the matrix C, diagonalizable.) We have
| V || $ [ill | 'I ((C))*
where we defined K; = | V I|. From Lemma A.2 we know that the assumption # 2 4,32 results in p (A) < - 2 Therefore, defining 7 == max and noting ((A) 15i5m
max / (C.), 1siSm
we obtain that
max 1sism
|C
| (1 1
In order to finish the proof we need to show that 7 < 5. For that, note that calculating the eigenvec- tors of C2 directly reveals that can represent this matrix
n
?
1+
V,
2
2
Since [. = =V /mmax (V.V.) and V7
V Amin (V.V?), we calculate V, V.V.T, which yields
2 no?
V.V.
17

---

Published as a conference paper at ICLR 2021
This representation allows to directly calculate the two eigenvalues of V. V,,", which shows that
Amax (V.V.)
Amin
(V.V,))
3 2 no?
+ V( + 2 2002
+4
2 2
V(1 1 + 2002
3 no?
1 + 2 yor
2
+
+
4 no7
2
2/
< 5,
noa
where the last inequality holds because of proof.
g. Since 7
max Ni. this finishes the 1sism
Now that we have shown that the linearized iterates converge the global optima turn attention to showing that the nonlinear iterates 16 are close to its linear counterpart 21. For that, we make the following assumptions.
Assumption 1: The singular values of the Jacobian initialization are bounded from below
Mmin (J (0o)) 2
for some positive constants a and B.
Assumption 2: In a neighborhood with radius R around the initialization, the Jacobian map- ping associated with obeys
[ (0) < B for all 0 E BR (0g). where BR (0.) = (0 E R&: 1|0 Oolle - R).
Assumption 3: In neighborhood with radius R around the initialization, the spectral norm of the Jacobian varies no more than in the sense that
1 (0) J (0o)l Se
for all 0 E BR (0o).
With these assumptions in place, we are ready to state the main theorem.
Theorem A.4 Consider the GDA updates for the min-max optimization problem 12
[ d + n ah de) 0++1
(22)
0, Voh dz)
and consider the GDA updates of the linearized problem 21
det1
[d, + p alimn 0, d.)
(23)
0
0, - -0--vel ohan 0,, de)
Set : rr
and Z,
where T. (0.) and F. f(0)) + To 0, 00)
di
d,
denote the residuals.
Assume that the step sizes of the gradient descent ascent updates satisfy # 8,3 well 0
18

---

Published as a conference paper at ICLR 2021
u. u 1. Moreover, assume that the assumptions 1-3 hold for the Jacobian J (0) of f (0) around the initialization 0g E R" with parameters a,, 3, c, and
3² a²
To
18c |
R 2y=2%
20
(24)
To
a
t
which satisfy 4y.c I a², Here, Y S 5 is a constant, which only depends on ps, tp and Jo- By To we denote the pseudo-inverse of the Jacobian at initialization Jo- Then, assuming the same initialization 0,- = 0. do = do (and, hence, 2u = zo). the thelowwngg holds for all iterations t 2 O.
lzell, converges 0 with a geometric rate, i.e.
Izelle S 53(1
1702 (1-1-1a)
||zolle..
(25)
The trajectories of 25 and žn stay close to each other and converge to the same limit, i.e.
(1 n7a²
(-1
2 Zelles - 2177? Be
2
(26)
4y2
$
11
e (155
16 a²
15)
The parameters of the original and linearized problems stay close to each other. i.e.
9e.8²²²
00-00
0, 0:
|
(27)
a
The parameters of the original problem stay close the initialization, i.e.
R 1 Oulle, - 2
(28)
Theorem A.4 will be the main ingredient in the proof of Theorem 2.1. However, as discussed in Section 2.4 we believe that this meta theorem can be used to deal with a much richer class of generators and discriminators.
A.3.1 PROOF OF THEOREM A.4
We will prove the statements in the theorem by induction. The base case for 0 is trivial. Now assume that the equations equation to equation 28 hold for r O,...,t t - 1. Our goal to show that they hold for iteration well.
Part I: First, are going to show that 02 BR (0o). Note that by the triangle incquality and the induction assumption we have that
00 lllee
110: 0--1 lle, |10 - -olles
R
10: 0.-1lle, ele,, 2
Hence, in order to prove the claim remains to show that 100, 0.-1lls
ile,, S 2. For that, we compute
||0: 01-1lle, - (0.-1) di
Tdh (0 1) J, 11 + +1|5" (0.-))l
do - -d.
1/
To d
+ +11J (0, -Joll |اا + +1[-T (0-1))l |r- - d.
||
0
482282 16
/
Td'
20
12
+c. +c.711z0lle, +
(15ln
15)
a2 ||zulles
(6)
|
[5]
38827²
7/02
To
2
+ a
|
12
19

---

Published as a conference paper at ICLR 2021
where y 2 5 is constant. Let us verify the last two inequalities.
Inequality (i) holds because
1 S 7/ g 02. and
To
VET
To
20
VE-WT 20
82
oi (wwi ro)² + (wi, do)²)
[oj
(wi; ro)² (() + (1ss; do) -32
To.
20
(29)
82
Also (i) follows from assumptions 1-3,
d dz-1
I - ž
together with induc-
12
tion assumption equation 26,
[d.-]
1 $1122-11e, S S11zolle,, and
To
To de
-1
5
Jo dz
1/
1/2
I
-n To
To P--2 Jot d
(1- 11
f/
I
-nJo To (1 (1-#)
6-1
To ro To do
S (1 - na?) 1-1
To
pl
To
20
122
(30)
where in the last inequality we applied Lemma A.3. Finally, by using 1 S
we arrive at
8D
Tj
3n
00 0c-1lles S m782
20
||00llea
0
To]
a²
ku
$
7
Jo
0
To.
20
+
3e7²
8a
1z0llea
R
K 2
where the last line is directly due to inequality (24), 7 S 5, and a S B. Hence, we have established O, E BR (Ou).
Part II: In Lemma A.3 showed that the time invariant system of state equations Σ,41 Az, is uniformly exponentially stable, i.e. || goes down to zero exponentially fast. Now by using the assumption that the Jacobian remains close the Jacobian the initialization To. we aim show the exponential stability of the time variant system of the state equations 16. For that, we compute
-
2, -1-1-11--1
Iul
(1 4)
21-1
-nJJoT
n (JoJo -Jt,--1T--)) di-1
21-+ +
Iul
(1 - u)
0
A A
20

---

Published as a conference paper at ICLR 2021
Now set == 1 1 nna.. By induction, obtain the relation 21 A'zu + Ei=o A A. Hence,
|
A'zo +
A
A
i=0
- || A'zolllz>
+
A 1111
82
$ 7
Ez0l +
7 ||11 (JoJo Je+1,iT,)) ||dille,
S 7 |0llle
+
m 1- (2 |
(31)
The second inequality holds because of Lemma A.3. The last inequality holds because by combining our assumptions to 3 with O, E BR (0o) and the induction assumption 28 for 0 S sist t 1, we have that
||JoH II+1,
|JoJo JoJ." + JoJ." II+I.T
< ||Jlll [1 - Jill +11 J++1, ||
- 8 I1To - -Vill + 3 B| J++1,el
$ 28c.
(32)
In order to deal with inequality 31, we will rely on the following lemma.
Lemma A.5 (Rugh, 1996, Lemma 24.5) Consider two real sequences p (1) and e (t), where p (1) O for all & 2 0 and
v
ift= 0
(1)
S
*b +
Σr(0()) 1/21 1
=0
where 1) and té are constants with 7) 2 0. Then for all 2 1 we have
(1) S 4
(1 + n (1+m.p(1)) (1)).
| and rewrite inequality
Now we define Φ,
2 6i.
d, 700
1=1
Hence, Lemma A.5 yields that
20yy3c
6, < 700
II
1 1
A
1=0
2
= 700
1 +
A
(
+ ?a22
700
2X
1
ga
2
y@u
1 naa
21

---

Published as a conference paper at ICLR 2021
where (i) follows from 4ryBe I a² and (ii) holds by inserting À na?. Inserting the definition of Φu and dr we obtain that
Izelles S> (1- na²
1|zolle.
2
This completes the proof of Part II.
Part III: In this part, our aim is to show that the error vector et == 2: - 2 obeys inequal- ity 26. First, note that
e, = 21 2t
(Azi-1 A1-1) A
Ae + A.-1
where in (*) used the same notation as in Part II for A1-1- Using recursive argument well as Eg = 0 we obtain that
||eele
Σ A
A
82
m (1 na --1-1 Aille
IA
1-1-; - "IJoTT my (1 (1-ma²)
Jtt1 ||l
IVE
2nBey (1 (1- (i-na?)=-1 1-1-1 ||z|les
The first inequality follows from the triangle inequality and Lemma A.3. Inequality (i) follows from the definition of A, Inequality (ii) follows from inequality 32. Setting e == 21y3e we continue
||eelee S
cy cy (1- - na²) (-12 1|zille2
c7² (1 - -na?) -)(2))=111 (1- na²
IA
|
1 ma²
t-1
cy²
|20lle2
(1 na? |zollez*
t-1
= 2 3
2
Here (iii) holds because of our induction hypothesis 25 and (iv) follows simply from 1 - ga² < 1 - na?
2 This shows the first part of equation 26 for iteration Finally, to de- rive the second part of equation 26 we observe that for all 2 0 and 0 S we have (1 x) el in 19
Since na 3 aaa
1632 TO we can use this estimate, which yields
|eellee S 23e 3e. (1 (1- na²
(-1
|
4-2 Be
< e
120 |z0lle2-
(15
In
10 a
Hence, we have shown equation 26.
22

---

Published as a conference paper at ICLR 2021
Part IV: In this part, aim to show that the parameters of the original and linearized problems close. For that, we compute that
1 0: 0
Veh (0, Vollnn (0;, dj)
12
fz (0:) d, - Jd'd,
[-1
(J (JT( Fo) d
J (0.) (d: - d.)
(d.-di)l
+
|| + Σ
|leille
1=0
1-1
1122
i-1
Σ (1
na 2) 12001e + 282
|
2
1=0
1=0
Here (i) follows from assumptions 2 and 3, and (ii) holds because of Lemma A.3 and our induction hypothesis 26. Hence, using the formula Eizo ir -(144x"11-(64 (x=1))z))
we obtain that
(x-1))
- (1
na 1-1 2
+ (t 1) () (1- no
1 - (1 na²)
0: -0, 0, 12
7e ||
21182-
1102
na²
7c |
+ +211822
na.
na²
2
(112)
8,32g
7 ||zllle2
1/0
9e,8222
na
where (tit) holds due to S y and 1 15 8²
a2. Hence, we have established inequality 27 for iteration
Part V: In this part, going to prove equation 28 for iteration t. First, it follows from the triangle inequality that
00
0olles
0
0
+ 0, 0 cs
9r,8292
0
0
+
|| 1
at
23

---

Published as a conference paper at ICLR 2021
where in the second inequality we have used Part IV. Now we bound follows
00
0
from above as
00
00/1
Σ To
de
7
1/2
To' d:
0=
TT/
0
11 na??)
77
0
To
20
==
182
1 -
(1 na²)²
Jo
1/7
na22
0
To
20
82
Ju
0
20
2
82
where (i) holds by equation 30 and (fi) holds by equation 29, Hence, it follows from the definition of R (equation 24) that
g²
Jo
0
9c.32,2
100 Bolle 5
+
Izolls
a²
0
Jo
a²
82
R
This completes the proof.
A.4 PRELIMINARIES FOR PROOFS OF RESULTS WITH LINEAR DISCRIMINATOR
LAYER GENERATOR AND
In this section, we gather some preliminary results that will be useful in proving the main results i.e Theorems 2.1 and 2.2. We begin by noting that Theorem 2.1 is an instance of Theorem A.4 with f (W)- = + +> V 6 (W zz). We thus begin this section by noting that f (W) can be rewritten as follows
n Σ & (w) 2,)
S()) = .
1 El o (w 2,)
Furthermore, the Jacobian of this mapping f (W) takes the form
I(W) n Σ (V diag (ø' (W 2;))) z
(33)
To characterize the spectral properties this Jacobian will be convenient to write down the ex- pression for J (W)) which has compact form
J(W)J(W) (V diag (Ø' (W 8 x. ) (diag (o' (Wzz)) VT 8z,)
(3)
Vdiag (ø' (W 2,) diag (s' (Wz,)) VT) 88 (2Tzz)
V diag
Σ 2 f 2,)
VT
n²
I.....
V
D².VI
n
24

---

Published as a conference paper at ICLR 2021
where D is diagonal matrix with entries
Du =
Σ 1=1
23 (w) zi)
= ='
(34)
122
and Z Raxd contains the 2, 's in its rows. Note that we used simple properties of kronecker product in (i) and (ii), namely (A @ B)" = A @ B" and (A @ BC & D = (AC') @ (BD). The next lemma establishes concentration of the diagonal entries of matrix D2 around their mean, which will be used in the future lemmas regarding the spectrum of the Jacobian mapping. The proof is deferred to Appendix B.I.
Lemma A.6 Suppose up R.d. is fixed vector, 21, 22, , Zn Rdd are distributed as (0, a and constitute the rows of Z E Randd Then for any 0 S 6 S 3 the random variable D z" o (Zw)lle, satisfies
(1- (D²) DD² (1 B)(
with probability at least - 2 (e- we have
no?
is
1a2 te 64
+e-and) where 01 is a positive constant. Moreover
E (D') = 0² nd
n(n 1(n-11)
2T
Furthermore, using the above equation we have
03 (d m-1
E [[W))((W)]]
VVT.
2n
A.5 LEMMAS REGARDING THE INITIAL MISFIT AND THE SPECTRUM OF THE JACOBIAN
In this section, state some lemmas regarding the spectrum of the Jacobian mapping and the initial misfit, and defer their proofs to Appendix B. First, we state a result on the minimum singular value of the Jacobian mapping at initialization.
Lemma A.7 (Minimum singular value of the Jacobian at initialization) Consider our GAN model with a linear discriminator and the generator being a one hidden layer neural network of the form + Vo(W2). where we have n independent data points 21, 22. ,2 E Rd distributed as N( La) and aggregated as the rows of a matrix Z Raxx, and V E Bmxk has i.idd (O, of) entries. We also assume that Wo E Raxa has i.dd (0, o.)) entries and all entries of Wo. V, and Z are independent. Then the Jacobian matrix at the initialization point obeys
Tmin (J(Wo)) (va-0)²k -1- 01+ vm + +1) (1+ 00001
d n-1
3
0 058
2n
with probability at least 1 constant.
3e 2m
2k (e-1 +e
n62
4x2
+ +e a where e₁ a positive
Next lemma helps us bound the spectral norm of the Jacobian initialization, which will be used later to derive upper bounds on Jacobian at every point near initialization.
Lemma A.8 (spectral norm of the Jacobian at initialization) Following the setup of previous lemma, the operator norm of the Jacobian matrix at initialization point Wo gxxd satisfies
I (1+0) (Vk+2/m)
+
/
d
n-1
0 0<0<
3 2
2n
with probability at least 1 - c- k:
c
222
1s
+
26 14 +
-e-annd) with e₁ positive constant.
The next lemma is adapted from Van Veen et al. (2018) and allows us to bound the variations in the Jacobian matrix around initialization.
25

---

Published as a conference paper at ICLR 2021
Lemma A.9 (single-sample Jacobian perturbation) Let V E R be matrix with i.d. N (0,03) entries,
W E Rexd, and define the Jacobian mapping ((W = (Vdiag (ø' (W 2))) @ z² Then, by taking Wo to be a random matrix with i.i.d N (0, en- tries, have
2kR
1 o. I1zlle,
2/m+
log
2
Oxc
[2kB
for all W E BRxx obeying W
Woll S R with probability least 1 e -
Our final key lemma bounds the initial misfit - yy V (Woz.) E.
Lemma A.10 (Initial misfit) Consider our GAN model with a linear discriminator and the gen- erator being one hidden layer neural network of the form - Vo(We), where we have independent data points 21,22, Ø2, ...... Zn RRd distributed as (0,, and aggregated as the of matrix Z E IRadd and V E 1Rmx has i.id N N(0 oz)) entries. We also assume that the initial Wo E Rxxd has i.dd (0, o%) entries. Then the following event
1 n
1
Vo (Wozi)
(1+
J Vdd + T 05853
/2T
holds with probability at least (k: c2m((1/77)
(a:0)
+ (0/ay/nd)
+e
with 02 a fixed
constant.
A.6 PROOF OF THEOREM 2.1
In this section, we prove Theorem 2.1 by using our general meta Theorem A.4. To do this we need to check that Assumptions 1-3 are satisfied with high probability. Specifically, in our case the parameter the matrix W and the non-linear mapping f is given by f (W) = 1. Σ. Vó (W z1). We note that in our result do 0 and thus | |ro l which simplifies our analysis.
To prove Assumption note that by setting
and r) = Y/ in Lemma A.7, we have
d
min (I (JWW)) 2 0,0;
2 V 302mmmmmmmmmmm V
2n
=: a.
This holds with probability at least 3e 12 4k -on 2k - zi8, concluding the proof of Assumption I. Next, by setting = in Lemma A.8 we have
d n-1
I1 (Wo)l SC = 2 Jonzz [Vk+2//
2n
with probability at least 1 T e on e- stc. Now bound spectral norm of Jacobian
at W where ||W - Wn || < R (the value of R is defined in the proof of assumption 3 below), we use triangle inequality to get
| (W)l I (Woll I|J (W)- J (Woll.
This last inequality together with assumption 3, which we will prove below, yields
a²
J (W))
IJ (W)l 1J + + 1 (Wo)l
< 1 (W
4yB
4,
26

---

Published as a conference paper at ICLR 2021
Therefore by choosing 2Ç arrive
| (Wo)l
1 (W)) 11 (Wo)ll
43
|J (Wo)ll
11 (W6)l
8C
I| (Wo)ll
11 (Wo)ll
8 (Wo)
< 2 (Wo)ll
2Ç B,
establishing that assumption holds with
d d+" n-1
B 30 (Vk - -2/m)
2n
with probability at least e 2k e-n k e- 216
Finally to show that Assumption holds, we use the single-sample Jacobian perturbation result of Lemma A.9 combined with the triangle inequality to conclude that
J (W; 24) - (Wo; 2:))
I (W) J (Wa) =
I (W: (Wo;
0e
n
2/m+
6
2kR
log
k
m
Ow
3
2 d/
( S 0
1Z F
2h:R
A
2/m+
log
TT
Tw
3
2h
3
5 Vo
2kR.
2/m+
log
(35)
2kR
where (1) holds by Cauchy-Schie Schwarz inequality, and (ii) holds because for a Gaussian matrix Z E gaxd with (0, o?) entries the following holds
IP ||2 S 5 o0= vnd nd
2 >P(1Z1
|1 S
3 0d?nd] 2 1 c- 74.
27

---

Published as a conference paper at ICLR 2021
Now a² and show that Assumption 3 holds with this choice of and with radius R, 1
whose value will be defined later in the proof. First, note that
a²
4yB
0. ( 1/ 9- -2/m)
d+ /d
2n
1270,0=
(Vi- + +-+mmm)
v
14t 1=1
2n
(6) Oy0= (1) .V 45
60
3/k
0,02v Vi
42000
where (i) holds by assuming k 2 C m with C' being large positive constant. Combining the last inequality with equation 35, we observe that a sufficient condition for assumption 3 to hold
5
2 ow
k
OOTVVK
4 -oo= Vd
2/m+
log
42000
2
which is equivalent to
2kR
105000 mdd 52500 Vd.
6
log
S Vk.
2
ow
Now the first term in the I.H.S. is upper bounded by / if term we need
(210000)² md, and for the second
2kR
k
105000 Vd-
6
log
S Vl.
3
2kR du
2R which by defining =3d
is equivalent to
owvk
x log
105000
This last inequality holds for logd with < sufficiently small positive constant, which translates into
R < c- DwVk
(36)
dd)
a² So far we have shown that Assumption holds with 4yB and with radius R defined as R = d. and conclude that it holds for any radius R less than R well. Now work with
(dlog
28

---

Published as a conference paper at ICLR 2021
the definition of R in equation 24 to show that R < R:
R
B2
To
9e0og2
1z00le2
= 7
20
at
82
( 8²
3242
$ 03
Isaalee
+
173
||rollez
13a
9
B
=
>7llrolle
a
(6))
32
20
a ||rolles
30,00 (vr+ + 2//)) v
|+==
n=1
2n
20
rolle
0.00 (3VK - 9- -9-2mm)
d+
2n
(ii1)
$ 0 0 (Gorowosvk d. m + |
[o S _ and 4y a², (ii) holds as 1 s and as we substitute
where (i) holds because
from Lemma A.3, and (tii) follows from k C and using d 3 in Lemma A.10. Now sufficient condition for equation 36 to hold that
Voo (3 V. d. m | Sc
ow V
(d d)
which is equivalent to
2
0oowa (dl d) Vk. d. m + (dlog d) ||=lle, S e. ko,0000.
Finally, this inequality is satisfied by assuming k 2 C mat log (d)² and setting 0.0 2 This shows that assumption holds with probability at least ne ne -omd log(d)? k om Toon
ma? do
kdt Toz, concluding the proof of Theorem 2.1.
A.7 PROOF OF THEOREM 2.2
Consider nonlinear least-squares optimization problem of the form
1 min (()) == || (0) - E1lr,
DERP
with f: RP + Rm and E Rm. Suppose the Jacobian mapping associated with f satisfies the following three assumptions.
Assumption We assume amin (J (0o)) 2 2a for a fixed point 0g E RP.
Assumption Let -| be a norm dominated by the Frobenius norm i.e. |10| < ||||| F
holds for all 0 E IR. Fix point On and number R > O. For any 0 satisfying 110 0ol S R, have || (0) I (0)) < 3-
Assumption We assume for all 0 E RP obeying |0 0oll < R, we have ||J (0)1 < B.
With these assumptions in place we are now ready to state the following result from Oymak & Soltanolkotabi (2020):
Theorem A.11 Given 0g E IR?, suppose assumptions 1, 2, and 3 hold with R IIf (0n) vlle,
(37)
29

---

Published as a conference paper at ICLR 2021
Then, using a learning rate 77 S 3,8 all gradient descent updates obey
Ilf (0,) vlle, - (1 - II (0o) -Vlla
(38)
We are going apply this theorem in our case where the parameter is W, the nonlinear mapping is (W) + -i=1 V (Wz+) with á ReLU, and the norm || set to the operator norm.
Similar to previous part, by using Lemma A.7 we conclude that with probability at least 1 3e 4k .e.e
en een 2k e zí8, assumption is satisfied with
+ 2-1
2a = 0,02
- 1-k--92vnm 2vm
Vk 2
2n
Next we show that assumption 2 is valid for a as defined in the previous line and for radius R defined later. First note that
000," vi.
where the inequality holds by assuming K 2 C m for a sufficiently large positive constant Now by using equation 35 assumption 2 holds if
5 oo I
2kR
h:
2/m+
6
log
sc.0,02- Vk.
no
3
2
which is equivalent to
$
12k
k
Imd+CVal
log
S Vk.
3
2h:1 d
The first term in the L.H.S. of the inequality above is upper bounded by V if t: 2 C md. For upper bounding the second term is sufficient to show that
2kR
k
CVd
log
S <Vk,
Ow
3
2
which by defining x 3d
is equivalent to x log (3) S S. Now this last inequality holds if we have log(d] for sufficiently small constant c, which by rearranging terms amounts
2R v
aw
to showing that I c.
Hence up to this point, we have shown that assumption holds with radius R = aav/ and this implies that holds for all values of R less than R.
(d-log(d))
(d)))
Therefore, work with the definition of R in equation 37 show that R S I as follows:
3 flf (0o) - vllez
R=
3 2 Tn Vk ..dd.... d. ||
(20 vk m. d 3 ||
0 (1 - 2/m
2n
where in (i) we used Lemma A.10 with = = Hence for showing R < it suffices to show that
2 (20 m d |
on Vi
0,0; (5Vb 2 m)
d+ 2n
(d log (d))
30

---

Published as a conference paper at ICLR 2021
which by assuming & 2 C. simplifies to ooDuo (d log (d))* Vk m m. (d log (d))* | S k. 0.0w0.
0.0000000-
Now this last inequality holds if & 2 C. mdd log (d)² and by setting doQwas mad log o Therefore Assumption 2 holds for radius R defined in equation 37 with probability at least 1
ne T ne-mmmdd log (d) k e
1500
Finally to show assumption holds, we note that for all W satisfying W Woll s R, where the value of R is defined in equation 37, it holds that
I (w)ll = IIT (Wo)ll + |1 (W) J (Wa)ll
$ || (Wo)ll +
min (I (Wo))
< ||J (Wo)ll +
6
< 21] (Wo)ll
+
50,00 (Vh: + 2/m)
V
2n
where the last incquality holds by using lemma A.8, hence establishing that assumption holds with
d
= 30 (V - 2\m²)
2n
with probability at least e 3 2k . e k. e 216, finishing the proof of Theorem 2.2.
B PROOFS OF THE AUXILIARY LEMMAS
In this section, we first provide a proof of Lemma A.6 and next go over the proof's the key lemmas stated in Section A.5.
B. PROOF OF LEMMA A.6
Recall that
(W)
Σ
(Vdiaglo' z:)z)))ae di)) ('((2,)) (2, 2,)
n i,=1
1
n
1 v D V",
diag l
Σ
2 ww 2i)
VT
n
n2
where D is diagonal matrix with entries
DEc Σ 2:00 (un? 2:)
-T
1' (Zun))
(39)
82
The matrix Z E Raxdd contains the z 's its rows. In order to proceed we are going to analyze the entries of the diagonal matrix 2 We observe that
Z ('w) Z 1|
(I
w
|| 2 00
(w))
+
w
00
Z
||w 12
First, we compute the expectation of A. We observe that
www
A
Σ
I
2z
(T))
w
|2
31

---

Published as a conference paper at ICLR 2021
Conditioned on w, tion V (0 w 2; is distributed as / (0. (I ww w
and w² 2, has distribu-
).
Moreover, these two random variables are independent, because w is in the This observation yields
null space of 1
www
B(A)
E
Σ II-
(w
zi)
[00]
7
ww"
www"
E
di(w""z))''" (w² (w²²z) z,) |2] ) E (1o'(1="2)))
2
| 1| )², o' d'(o" zi)00
2
j=l
(|1T-110
www
||20 2z
2 (d 1)o² n (d 1)02.
2
Next we show that A is concentrated around its mean. Because (I- wow" - [-]]]
2; is independent from
2 Zi, we use z as an independent copy of 2;. Hence we can write
ww T
= Ø' (Zw)
| 1
" T
1 03 Z mn
| 12
www
2z,0' (w 21
Σ g:ug U1
|w
and u, o' (wT²!) bern(t),* and these are all independent from each other. Note that |E g:u: 122 has the same distribution as I|le| ||ull where g N (0, o3 (I- ||l|l ) and is a vector with entries u, Note that for the norm of u, the event
where g:
2; N (0.02 (I- une""
wi
wo""
2 (1 8) S |uu| 12 S n
(1+
2
holds with probability at least 1 2e nd²
Recall that for g ~ N(0, (2)) and ò < 1/4 we have
P [1g l2. 2 (1 + 5) (Ig1l ) S 25²
(40)
P [191 l2, < (1 - 5) (1111(.)
S e dda
By applying the union bound and noting that E (19112.) that the event
(d - 1) of, for 0 < 8 < 3. obtain
||g 22 |/ (d 1-o s 8 (d 1)02
*Here, bern( means that the random variable takes values 0 and each with probability 1/2.
32

---

Published as a conference paper at ICLR 2021
no?
dea 54
holds with probability at least - 2e In order to analyze B, first note that
2e
ww
zT Φ (Zw)
w
T
z
8 (ww)
2
|| 1
w
Z Zww
w
(g.
(1(lw)
[g)]
Σ ReLU(a))
Σ 9i 1 20)
==1
where 9: = = m
(0, It follows that
(B) E
Σ
(eiU(gi)
Σ
E ReI.U2(
Σ (イ
B (ReTU())))eTU()))
+
1=1
n
ann 1)
0
+
2
2T
which results in
E (D - = nd
:n(nn-)) isesk. 2x
+
2
Next, in order to show that concentrates around its mean, we note that ReLU (gi) is a sub- Gaussian random variable with 1/2 d norm Co., where C' is fixed constant. Therefore X Σ ReLU (g.) is sub-Gaussian with 1/2 noom Cyno, By the sub-exponential tail bound for
X2 E we obtain
P( - (B) S 2e
Finally by putting these results together and using union bounds have
D E (D
2 SE (D+)
< 2e 4
+ 2e
243
c:
0 8 <
3 2'
finishing the proof of Lemma A.6.
B.2 PROOF OF LEMMA A.7
Our main tool for bounding the minimum singular value of the Jacobian mapping will be the fol- lowing lemma from Soltanolkotabi (2019):
Lemma B.1 Let E B& be a fixed vector with nonzero entries and D diag (d) Also, let
A k have i.i.d. N (0. 1) entries and T _R Define
by (d) E Dgll,,,
where g ~ NO, Ix). Also define
o (T) == max ||a|les vET
Then for all E T we have
|| by (d) | 5 ||dll,., w (T) +
with probability at least
be slall +(()
33

---

Published as a conference paper at ICLR 2021
In order apply this lemma, set the elements of d to be Dee in equation 39 and choose = 5mm1 and A V E Rkxm with N N(0, o.)) entries. It follows that
by (d) = E Dglla
R (Dgllia)
Var (1
where
A E ((Dgl)) = ||dl - D DD:
We are going to use the fact that for B-L.ipschtzz function & and normal random variable ~ (0,, 1), based on the Poincare inequality (Ledoux, 2001) we have Var(ó (g)) S B², By noting that for diagonal matrix D
Drlle, - -DDylle -
Dz Dyllez I $|d|le x ylles
we get
Dglle, = (igl(2.) Dglle,
v
I|dll Idll
This combined with w (sm-1) $ m and Lemma B.I yields that the event
min (VD) 2 ou (Viddle ||dli__ ||ll vm (m-1)) 7)
(41)
holds with probability at least 1 - 3e "Id1
Next, using the concentration bound for D which obtained in Section B.1, we bound ||d|? and ||d]le.. where we have set d, Då for 1 S i k. For 0 s 8 S 3 we compute that
P max d, 2 (1+ 6) /B( Isisk
= P U
(1+))
< k: PP
d 21+ [(+
Pd.
S k (e naa
+
+ cind
(42)
as well
||dlle, (11-0) vk E(d
SP U < (1
k d S <1 -1- E)
< k P d < (1 5) [d)) S k- (e n52 +e + -1in
262
(43)
Finally by replacing with n [|d]] e_ /m in equation 41, combined with equation 42 and equa- tion 43, for random Wo with i..d. N (0, o.) entries have:
1
Omin (J(Wo)
min (VD)
(11--) - 8)2 k - -1++)) V vm(1+ V [df)
n
d m-1
3
(1 - 8)² k- (1 8)2
vm (1 7) (1 5) 0.00
0 5 8
2n
with probability at least of Lemma A.7.
3e
2m
8
E
n 18
2z2 +e
+ + )n= This completes the proof
34

---

Published as a conference paper at ICLR 2021
B.3
PROOF OF LEMMA A.8
Recall that
JWW)
1 n² t=....
V diag
Σ 2 ww 2i)
r
1 - V vT,
D² V.
which implies that
1 VV D n
IJ(WW)
V D||
For matrix V E R with i..d (0, ( the event
[V] S (Vk + 2/m
holds with probability least - Regarding matrix D by repeating equation 42 the following event
nd 2
+ n(n 1)
3 2
DI
(1 max Du s (1+ V = (1+))oz Isisk
0 H
2x
holds with probability at least 1 1- k. (6- _ te- 31 + t e Putting these together it yields
that the event
I(W))l S (1+5)a,0 (Vi: (Vh++v 2/m)
V
d n-1
0 0585 3
2n
holds with probability at least - c k (e- Lemma A.8.
n62
+
262
65
+ e
e-aind)
finishing the proof of
B.4 PROOF OF LEMMA A.10
First, note that if W has i..dd N (0, entries and V, W, Z are all independent, then Ilf (Wille,
Vo (WZT) lax1 le, has the same distribution as ||e|le, ||alle,, where v 1 (WZ") 1 has independent sub-Gaussian entries, so its 22-norm is
N (0, (m) and concentrated. Note that conditioned on W. a; Eド= ReLU (2, ww. is sub-Gaussian with ||a:ll,s ll, = - [IW.lle,.= a= Vn
and it is concentrated around Ea, = V2x ||w: 0z. This gives
(2a,))
((, S (1 + 5),a,, 2 -
1 bz
-on5
which implies that
PP (a < 36)+33) 38) 2 (1+
- enn
05d
Due to the union bound we get that
P |alle (1+ 8) Σ [E,,)
SP
01+ (Ea:)²
i=1
{ag 2 (1+ (Ea:)) s con(//3) 05853.
By substituting Σt_ (Ea,)² 2/ o [ || this shows
P Pllllles (1 +
1
02 W | }
2 p
1 |aall (1 +
2
2 k. e (6(33))
05053.
V2T
2T
F
35

---

Published as a conference paper at ICLR 2021
We also have the following result for ~V(00, om
P (lolle s (1+ o. m 2 -t -m
By combining the above results we obtain
P Iallee llalle s 61+
1
oo v m
W
2 Ilall 11llle, $ (1 (1+ 5/3)2
V2T 0,00 V [ |
1
V2T
21 - ko cm((//))
1m/3)
0 05853,
Furthermore, we can bound || [ by the tail inequality
P , s (1+ ow kd
2 1 1-- Am
Hence, by combining the last two results we have that
P Iaalle llolle, S (1 + 8)
1
o 0w Vk d m)
Iaale l1allez S (1+
1
0 g0
Fw
V d m.
22T
V2T
2 1 - k k.e com(6/27) 10/0;3m
16/3
2
0 O5053.
Therefore, due to the triangle inequality the event
(I(W)) E1ee2 I (1+
0 V d m |
05053
2
holds with probability least k -0l----2nmdppp -2m(6/27)) -c (8/0) C22 completing the proof of Lemma A.10.
(8/3)
for some positive constant
C ADDITIONAL EXPERIMENTS
Effect of single component overparameterization:: In Section of the main paper, we performed experiments in the setting where the size of generator and discriminator (both discriminator and generator uses the same value of k). In this part, we analyze single- component overparameterization where we study the effect of overparameterrization when of the components (generator / discriminator) has varying k, while the other component uses the stan- dard value of k (64 for DCGAN and 128 for Resnet GAN). The FID variation of single-component overparameterization are shown in Fig. 7. We observe similar trends as the previous case where increasing overparameterization leads to improved FID scores. Interestingly, increasing the value of k beyond the default value used in the other component leads to a slight drop in performance. Hence, choosing comparable sizes of discriminator and generator models recommended.
held roughly the same
D EXPERIMENTAL DETAILS
The model architectures use this in the experiments shown in Figure 8. In both DCGAN and Resnet-based GANs, the papemeter l controls the number of convolutional filters in each layer. The larger the value of is, the more overparameterrzed the models are.
Optimization: Both DCGAN and Resnet-based GAN models are optimized using the commonly used parameea:: Adam with learning rate 0.0001 and betas (0.5, 0.999) for DCGAN, gradi- ent penalty of 10 and 5 critic iterations per generator's os's iteration for both DCGAN and Resnet-based GAN models. Models are trained for 300, 000 iterations with batch size of 64.
E NEAREST NEIGHBOR VISUALIZATION
In this section, we visualize the nearest neighbors of samples generated using GAN models trained with different levels of overparameterizztton. More specifically, we trained a DCGAN model with A = 8 and & 128, synthesize random samples from the trained model and query the nearest neighbors in the training set. The plot of obtained samples is shown in Figure. 10. We observe that overparameterizeed models generate samples with high diversity.
36

---

Published as a conference paper at ICLR 2021
Test FID
Test FID
60
FID Score
FID Score
50-
50-
40
Hidden Dimension (k)
Hidden Dimenston (k)
(a) Discriminator overparameterization
(b) Generator overparameterization
Figure 7: Single Component Overparamterization Results: We plot FID scores Resnet GAN the hidden dimension of one of the components varied, while the hidden dimension of other component is held fixed. Even this case, overparamettrizatioo improves model convergence.
Conv: 3x3, s1 (K)
Linear > 8K
ResBlock (k]
Linear >> (k)
ResBlock (K)
Axx, (2k)
ConvT: (4k)
ResBlock
ResBlock (i)
Conv: Ax4, 52 (4k)
ConvT: 4x4, s2 (2k)
ResBlock
ResBlock (k)
Conv
Conv: 4x4, <2 (8k)
ConvT: Ax4, x2 (K]
ResBlock (k]
ResBlock (k)
Conv (k)
Linear
4x4, (3)
ResBlock (i)
Discriminator
Generator
Discriminator
Generator
DCGAN
Resnet
Figure 8: Architectures used over-vevvaate wve--parameterization experiments. The number of out-channels in convolutional layers is indicated in red. Parameter & controls the width of the architectures larger the k. more over-parameterized the models are.
Diar: Itern
der
MSE
Final MSE
1.0
Final MSE
1.0
Disc ibere dur
0.75
0.50
0.5
0.25
12
1024
1004
1034
Hidden Dimension
Hidden Dimension
Hidden Dimension (k)
(a) Discriminator trained to optimal-
(b) Gradient Descent Ascent
(c) diter steps of discriminator
ity
date per generator iteration
Figure 9: Convergence plot GAN model trained on the Two-Moons dataset, with linear discrim- inator and 1-hidden layer generator as the hidden dimension (k) increases. Overr-arameterrizate models show improved convergence
37

---

Published as a conference paper at ICLR 2021
Nearest ne ghborr in training set
Nearest ne hbbrr in training set
Generated samples
Generates atd samplees
k=8
k=128
Figure 10: Nearest neighbor visualization. We visualize the nearest neighbor samples in training set for generations from DCGAN model trained on CIFAR-10 dataset. Left panel shows DCGAN trained with & = 8, while the right one shows the one with k 128. We observe that overparame- terized models generate samples with high diversity.
38


Reviews:
[{"review_id": "vnKpWPfZrS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nWhile much work has been devoted to understanding the role of the discriminator in GAN training, comparably little is known about the role of the generator. \nIn this work, the author address this important question, more exactly the role that generator overparametrization plays in GAN training.\nEmpirically, the authors show that when applying DCGAN and RESNET architectures to CIFAR10 and CELEBA, increasing the number of parameters in the hidden layers decreases the Frechet inception distance and improves image quality.\nTheoretically, they show that RELU networks with a single hidden layer converge to the global minimum under simultaneous gradient descent with high probabiliy, provided that the dimension of the hidden layer is large enough.\n\nRecommendation:\nI think that this work makes a contribution to an important topic that has not been studied very much, so far. My main concern is that I find the presentation somewhat lacking at this point. In particular, as detailed below, I would appreciate a discussion of overparametrization vs model complexity. I would also suggest to the authors to consider beginning by presenting their experiments on real GANs to describe the empirical phenomenon that their theorem is supposed to illuminate.\nFinally, I believe that some additional guidance in interpreting the results of the theorem would be helpful. In particular, the comparison of the setting of Theorems 2.1 and 2.1 should be more prominent since the difference between these two result is what really captures the relationship to GANs, as opposed to arbitrary RELU models.\n\nQuestions/Suggestions\n- How do the authors define \"overparametrization\"? In particular, how is it different from model complexity. It is not clear to me why Figure 1 should concern \"overparametrization\" as opposed to model complexity? I understand that in the deep learning setting these concepts might not be easy to differentiate, in either way I believe some more background on this topic would be warranted. Similarly, a key element the lower bound on $k$ in the theorem seems to be that ensures that minimization objective has optimal value of zero, that is the \"data\" can be reproduced exactly.\nThis again seems to me to rather be about model complexity than about overparametrization of the model. Looking at the proof it seems that the concentration argument leading to a well-conditioned Jacobian does not depend on model being perfectly able to represent the \"training data\". This might be worthwhile to explain in more detail in the paper. \n\n- \"The networks are optimized using Gradient Descent/Ascent (GDA) to reach a saddle-point of the min-max optimization problem.\"\nThere have been multiple recent works such as [Berard et al.](https://arxiv.org/abs/1906.04848) [Farnia and Ozdaglar et al, 2020](https://arxiv.org/abs/2002.09124), [Schafer et al.](https://arxiv.org/abs/1910.05852) that call the role of nash-equlibria/saddle points into question. I think the authors should engage, at least briefly, with this line of work.\n\n- \" One of the key factors that has contributed to the successful training of GANs is model overparameterization. By increasing the complexity of discriminator and generator networks, both in\ndepth and width, recent papers show that GANs can achieve photo-realistic image and video synthesis (Brock et al., 2019; Clark et al., 2019; Karras et al., 2019).\" \nThis seems a bit misleading since at least the Karras et al. work suggests much more specific modifications than just increasing the complexity. I don't think any of the references listed support the claims about the importance of overgenearlization as much as the way in which they are cited suggests.\n\n- \"In particular, it has been empirically observed (as we also demonstratein this paper) that when the generator/discriminator contain a large number of parameters (i.e. are sufficiently over-parameterized) GDA does indeed find (near) globally optimal solutions. In this section we wish to demystify this phenomenon from a theoretical perspective.\" \nThis statement should be provided with some evidence. it is also not clear what a (near) globally optimal solution means. In the context of GANs, [Arjovsky and Bottou 2017](https://arxiv.org/abs/1701.04862), [Berard et al.](https://arxiv.org/abs/1906.04848), [Schafer et al.](https://arxiv.org/abs/1910.05852) show that GANs do not even converge to (nearly) locally optimal points, despite producing good images, contradicting the statement.\n\nminor points:\n- \"very simpler\" -> much simpler\n\n================================================================================================\n\nAfter reading the author's response and the other reviews I still lean slightly towards acceptance and have therefore left my rating unchanged.\nWhile not being an expert on the subject, I find the work interesting. In case the paper gets rejected, I recommend to the authors to the feedback provided by the referees to clarify the narrative of the paper. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "m-271amD_tX", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies how over-parameterization plays a role in GAN training. Theoretically, it shows that a GAN with over-parameterized 1-layer neural network generator and a linear discriminator can converge to global saddle point via stochastic optimisation. Similar results are obtained for nonlinear generators and discriminators under some conditions. It also provides empirical results to support its findings. \n\n## Pros\n\n- The paper is easy to read.\n- The result can be significant as it suggests we simply need larger GANs in practice.\n\n## Cons / Questions\n\n- I'm not sure if the term over-parameterization is well-defined in the paper. For training neural classifiers, the word \"over\" is clear because of the transition point of the double descending curve. But here we only see a descending curve (for performance) within the regime of parameter space the paper studies. To be more specific, is $k=256$, which is only 2x or 4x of common choices of feature numbers, considered as over-parameterized? Similar for Figure 2, is $k=1024$ for linear layers over-parameterized?\n- The paper says, \"One of the key factors that has contributed to the successful training of GANs is model over-parameterization\". But in fact, a lot of works have been showing that a careful balance of generator and discriminator capacity is in fact important, which is also agreed by the authors in the end of Section 3. So, I'm not sure if this opening sentence is a valid claim.\n- The empirical results are based on DCGAN and Resnet that use convolutions. Does similar result hold for MLPs? Testing it on MNIST may be useful.\n- Can you explain how step sizes and other parameters are set while varying the capacity of GANs?\n- The study on generalization gap seems to be incomplete. In particular, we also need to check the GANs simply memorizes the data while increasing the capacity, right? It's unclear if a dropped FID in both train and test (i.e. Figure 5) can rule out this issue. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "lw40isQIKem", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors proposed to analyze the over-parameterization in GANs optimized by the alternative gradient descent method. Specifically, considering a GAN with an over-parameterized G and a linear D, the authors proposed the theorem 2.1 to provide a theoretical convergence rate in GAN’s training.\n\nHowever, this paper is problematic. The details are as follows:\n\n1. The gap between the paper’s title and theoretical claims. To my best knowledge, the OVER-PARAMETERIZATION means that the model will overfit to the training data and cannot generalize to test data. Thus, the generalization bound between training error and the test error is the main concern in this topic. However, in this paper, the authors mainly focus on the convergence rate during the training. I think this topic is more correlated to the non-convex optimization problem, rather than the over-parameterization problem.\n\n2. The theoretical claims in Sec 2 are not convincing. First, what is the data distribution? In the whole Sec 2, there is no detailed explanation about the data distribution, which is one of the most important parts of the analysis. Only the `Numerical Validation` part mentioned that the data distribution is a univariate Gaussian. Though we assume that the data is Gaussian, simply minimizing the distance between the mean of data and the ones of G is not enough: the variance in the data is not taken into consideration. I’m not sure that using a linear discriminator is enough for G to model the data distribution; generally, we assume the discriminator has infinity capacity.\n\n3. The theoretical derivation is ambitious. In Theorem 2.1, why $V$ is not optimized in Eqn. (2) & (3)? In Theorem 2.3, why $f$ is a general mapping? In GANs, it should be a parametric mapping from z to x. Besides, Theorem 2.3 claims that it is a general minimax problem. However, it is still restricted to a linear discriminator. Clarity needs to be improved.\n\n4. Finally, the experimental results cannot fully validate the authors’ claims. In Fig. 4, with smaller k, G’s capacity is not sufficient to capture the data distribution. In this case, comparing the convergence rate is unfair. Further, the paper does not provide any bound on the gap between training error and test error. I don’t know the purpose of Fig. 3 and Fig. 5.\n\nThree related work:\n[*1] talks about the existence of the equilibrium of GANs’ minimax problem. If the equilibrium does not exist, then the convergence rate cannot validate any claims as I mentioned above.\n[*2] also uses control theory to understand GAN’s training and [*3] adopts control theory to improve the training dynamics of deep models. The relationship should be discussed.\n\n\n[*1] Farnia, Farzan, and Asuman Ozdaglar. \"GANs May Have No Nash Equilibria.\" arXiv preprint arXiv:2002.09124 (2020).\n\n[*2] Xu, Kun, et al. \"Understanding and Stabilizing GANs’ Training Dynamics using Control Theory.\"\n\n[*3] An, Wangpeng, et al. \"A PID controller approach for stochastic optimization of deep networks.\" Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2018.", "extra_scores": {}, "extra_text": {}}, {"review_id": "l8pYiBFtoXr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\nThis paper studies the effect of model over-parametrization in GANs. While there is a lot of work on this in the supervised learning setting of classification/regression there is not much in the GAN framework where the minimax objective function complicates such an analysis. This paper considers two types of training of the GAN model, one with the simultaneous gradient descent ascent and one where the discriminator is trained to optimality for every generator update. It provides global convergence results under both algorithms in the case of a generator network with one hidden layer that is large enough and a linear discriminator.\n\n# Contributions: \nGiven the importance of over-parametrization of neural networks for better performance and low generalization error this work is a step toward a theoretical understanding of this phenomena in the GAN setting. Even though the global convergence results are provided in a simple setting, the proof techniques using dynamical systems and control theory might be useful for extending these results to a more general framework. \n\nThe comparison between convergence rates of the two training algorithms is also interesting. \n\nThe experimental evidence seems compelling, although it would be nice to consider examples other than simple gaussians for a more comprehensive empirical analysis. \n\n# Comments: \n1. It would be nice to compare the two types algorithms considered in terms of empirical evidence. For example a combination of the two plots in Figure 2 would be nice in order to get a sense of the effects of the two theorems 2.1 and 2.2 empirically. \n2. Just out of curiosity can we say anything about the training of the discriminator for a finite number of steps and how that affects convergence? Sort of as an interpolation between the two algorithms. \n3. A little more variety in the toy empirical examples considered would be nice but not crucial. While the experiments on the real data are compelling it would be nice to have empirical evaluations where we can compute the true generalization error or know the ground truth which is not simply Gaussian. \n4. It would also be nice if the authors could provide a summary of the proof of the main theorems either in the main paper or at least at the beginning of the appendix jus to provide a rough sketch of what pieces are required to show such a result.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: ### Paper summary 
This paper investigates theoretically and empirically the effect of increasing the number of parameters ("overparameterization") in GAN training. By analogy to what happens in supervised learning with neural networks, overparameterization does help to stabilize the training dynamics (and improve performance empirically). This paper provides an explicit threshold for the width of a 1-layer ReLU network generator so that gradient-ascent training with a linear discriminator yields a linear rate of convergence to the global saddle point (which corresponds to the empirical mean of the generator matching the mean of the data). The authors also provides a more general theorem that generalizes this result to deeper networks.

### Evaluation
The reviewers had several questions and concerns which were well addressed in the rebuttal and following discussion, in particular in terms of clarifying the meaning of "overparameterization". After discussing the paper, R1, R2 and R4 recommend acceptance while R3 recommends rejection. The main concern of R3 is that the GAN formulation analyzed in the paper is mainly doing moment matching between the generator  distribution (produced from a *fixed* set of latent variables z_i) and the empirical mean of the data. R3 argues that this is not sufficient to "understanding the training of GANs". At least two aspects are missing: how the distribution induced by the generator converges according to other notion of divergence (like KL, Wasserstein, etc.); and what about the true generator distribution (not just its empirical version from a fixed finite set of samples z_i)? While agreeing these are problematic, the other reviewers judged that the manuscript was useful first step in understanding the role of overparameterization in GANs and thus still recommend acceptance. And importantly, this paper is the first to study this question theoretically.

I also read the paper in more details. I have a feeling that some aspects of this work were already developed in the supervised learning literature; but the gradient descent-ascent dynamic aspect appears novel to me and the important question of the role of overparameterization here is both timely, novel and quite interesting. I side with R1, R2 and R4: this paper is an interesting first step, and thus I recommend acceptance. See below for additional comments to be taken in consideration for the camera ready version.

### Some detailed comments
- Beginning of section 2.3: please be clearer early on that you will keep V fixed to a random initialization rather than learning it. The fact that this is standard in some other papers is not a reason to not be clear about it.
- Theorem 2.2: in the closed form of the objective when $d$ is explicitly optimized, we are back to a more standard supervised learning formulation, for example (5) could look like regression. The authors should be more clear about this, and also mention in the main text that the core technical part used to prove Theorem 2.2 is from Oymak & Soltanolkotabi 2020 (which considers supervised learning). This should also a bit more clear in the introduction -- it seems to me that the main novelty of the work is to look at the gradient-descent dynamic, which is a bit different than the supervised learning setup, even though some parts are quite related (like the full maximization with respect to $d$).
- p.6 equation (8): typo -- the  $-\mu d_t$ term is redundant and should be removed as already included from $\nabla_d h(d,\theta)$.
- p.7 "numerical validations" paragraph: Please describe more clearly what is the meaning of "final MSE". Is this a global saddle point (and thus shows the limit of the generator to match the empirical mean), or is this coming from slowness of convergence of the method (e.g. after a fixed number of iterations, or according to some stopping criterion?). Please clarify.

Decision: Accept (Poster)