SGD Learns One-Layer Networks in WGANs
Authors: Qi Lei
Jason D. Lee
Alexandros G. Dimakis
Constantinos Daskalakis
Venue:  (2020)
Keywords: Wasserstein GAN
global min-max
one-layer network

Abstract: Generative adversarial networks (GANs) are a widely used framework for learning generative models. Wasserstein GANs (WGANs), one of the most successful variants of GANs, require solving a minmax problem to global optimality, but in practice, are successfully trained with stochastic gradient descent-ascent. In this paper, we show that, when the generator is a one-layer network, stochastic gradient descent-ascent converges to a global solution in polynomial time and sample complexity.

Under review as a conference paper at ICLR 2020
SGD LEARNS ONE-LAYER NETWORKS IN WGANS
Anonymous authors
Paper under double-blind review
ABSTRACT
Generative adversarial networks (GANs) are a widely used framework for learning generative models. Wasserstein GANs (WGANs), one of the most successful vari- ants of GANs, require solving minmax optimization problem to global optimality, but are practice successfully trained using stochastic gradient descent- In this paper, we show that, when the generator is one-layer network, stochastic gradient descent-ascent converges a global solution with polynomial time and sample complexity.
INTRODUCTION
Generative Adversarial Networks (GANs) (Goodiellow et al. 2014) are prominent framework for learning generative models of complex, real-world distributions given samples from these distributions. GANs and their variants have been successfully applied numerous datasets and tasks, including image-to-image translation (Isola et al. 2017), image super-resolution (Ledig et al. 2017). domain adaptation (Tzeng et al.) (017). probabilistic inference (Dumoulin et al., 2016). compressed sensing (Bora al.) 2017) and many more. These advances owe part the success of Wasserstein GANs (WGANs) (Arjovsky et al. 2017: Gulrajani et al. 2017), leveraging the neural net induced integral probability metric to better measure the difference between a target and generated distribution.
Along with the descr-dd empirical successes, there have been theoretical studies of the statistical properties of GANs
e.g. (Zhang et al.] 2018: Arora et al., 2017 2018; Bai et al., 2018; Dumoulin Dumoluumoulnn et al. 2016) and their references. These works have shown that, with an appropriate design of the generator and discriminator, the global optimum of the WGAN objective identifies the target distribution with low sample complexity.
On the algorithmic front, prior work has focused the stability and convergence properties of gradi- ent descent-ascent (GDA) and its variants in GAN training and more general min-max optimization
problems; see e.g. (Nagarajan & Kolter 2017 Heusel et al. 2017 Mescheder et al., 2017: 2018
Daskalakis et al. 2017 Daskalakis & Panageas 2018a b) Gidel et al. 2
& Stokes 2019
Mokhtari al.) 2019 Jin al.) [219 Lin et al. 2019) and their references. It is known that, even in min-max optimization problems with convex-concave objectives, GDA may fail to compute the min-max solution and may even exhibit divergent behavior. Henee, these works have studied condi- objective, tions under which GDA converges to globally optimal solution under nonconvex-nonconeas or different types of locally optimal solutions under nonconvex-concan or objectives. They have also identified variants of GDA with better stability properties in both theory and practice, most notably those using negative momentum.
In the context of GAN training, Feizi et al. (0177) show that for WGANs with linear generator and quadratic discriminator GDA succeeds learning a Gaussian using polynomially many samples in the dimension. In the same vein, are the first to knowledge study the global convergence properties of stochastic GDA in the GAN setting, and establishing such guarantees for non- non-linear generators. In particular, we study the WGAN formulation for learning a single-layer generative model with some reasonable choices of activations including tanh, sigmoid and leaky ReLU.
Our contributions. For WGAN with a one-layer generator network using an activation from large family of functions and quadratic discriminator, we show that stochastic gradient descent-ascen learns target distribution using polynomial time and samples, under the assumption that the target distribution is realizable in the architecture of the generator. This is achieved by a) analysis of the dynamics of stochastic gradient- and b) appropriate design of the discriminator to ensure a parametric O (z) statistical rate (Zhang
show it attains global optimum of the minmax problem.
et al. 2018 Bai et al. 2018

---

Under review as a conference paper at ICLR 2020
Related Work. We briefly review relevant results in GAN training and learning generative models:
Optimization viewpoint. For standard GANs and WGANs with appropriate regularization, Nagarajan & Kolter (2017), Mescheder et al. (2017) and Heusel et al. (2017) establish sufficient conditions to achieve local convergence and stability properties for GAN training. At the equilibrium point, if the Jacobian of the associated gradient vector field has only eigenvalues with negative real-part the equilibrium point, GAN training is verified to converge locally for small enough learning rates. A follow-up paper by (Mescheder al. 2018) shows the necessity of these conditions by identifying a prototypical counterexample that is not al always locally convergent with gradient descent based GAN optimization. However, the lack of global convergence prevents the analysis to provide any guarantees of learning the real distribution.
The work of (Feizi et al., 2017) described above has similar goals as our paper, namely understanding the convergence properties of basic dynamics in simple WGAN formulations. However, they only consider linear generators, which restrict the WGAN model to learning a Gaussian. Our work goes step further, considering WGANs whose generators are one-layer neural networks with broad selection of activations. We show that with a proper gradient-based algorithm, we can still recover the ground truth parameters of the underlying distribution.
More broadly, WGANs typically result in In these problems, a global min-max solution may not exist, and there are various notions of local min-max solutions, namely local min-local max solutions Daskalakis & Panageas (2018b), and local min solutions of the max objective Jin et al. (2019), the latter being guaranteed to exist under mild conditions. In fact, Lin et al. (2019) show that GDA is able to find stationary points of the max objective in nonconvex-concave objectives. Given that GDA may not even converge for convex- concave objectives, another line of work has studied variants of GDA that exhibit global convergence to the min-max solution Daskalakis et al. (2017): Daskalakis & Panageas (2018a); Gidel et al. (2019); Liang & Stokes (2019): Mokhtari ct al. (2019), which is established for GDA variants that add negative momentum to the dynamics. While the convergence of GDA with negative momentum is shown in
-onooooceeeee min-max optimization problems.
settings, there is experimental evidence supporting that it improves GAN
training (Daskalakis al. 2017 Gidel al. 2019).
Statistical viewpoint. Several works have studied the issue of mode collapse. One might doubt the ability of GANs to actually learn the distribution vs just memorize the training data (Arora et al. 2017 2018. Dumoulin et al., (016). Some corresponding cures have been proposed. For instance Zhang ct al. 2018); Bai et al. (2018) show for specific generators combined with appropriate parametric discriminator design, WGANs can attain parametric statistical rates, avoiding the exponential in
dimension sample complexity (Liang 2018 Bai et al. 2018 Feizi et al. 2017).
Recent work of Wu et al. (2019) provides algorithm to learn the distribution of single-layer ReLU generator network. While our conclusion appears similar, our focus is very different. Our paper targets understanding when a WGAN formulation trained with stochastic GDA can leam in polynomial time and sample complexity. Their work instead relies on a specifically tailored algorithm for learning truncated normal distributions Daskalakis et al. (0188.
PRELIMINARIES
We consider GAN formulations for learning a generator GA R + Rd of the form 2 + x = ((Az). where d parameter matrix and ó some activation function. We consider discriminators D. Rd + R Dv Rd + R that are linear or quadratic forms respectively for the different purposes of learning the marginals or the joint distribution. We assume latent variables are sampled from the normal (0, I where Iack denotes the identity matrix of size k. The real/target distribution outputs samples x D G- (A' Jkg ,, for some ground truth parameters A", where A is d x ku, and we take k 2 ko for enough expressivity, taking k = d when ko is unknown.
The Wasserstain GAN under our choice of generator and discriminator is naturally formulated as:
min max (S(A, v) Do(m) Ea Do T
Aggaxi wERd
We will replace by V E R when necessary.
2

---

Under review as a conference paper at ICLR 2020
We use a, to denote the i-th vector of A. We sometimes omit the 2 subscript, using ||=||| to denote the 2-norm of vector æ, and ||X]| to denote the spectral norm of matrix X. S" C Rux" represents all the symmetric matrices of dimension x We use Df [B) to denote the directional derivative of function f at point Xo with direction B: [B] = lim -
WARM-UP: LEARNING THE MARGINAL DISTRIBUTIONS
As warm-up, we ask whether simple linear discriminator is sufficient for the purposes of learning the marginal distributions of all coordinates of 'D. Notice that in our setting, the i-th output of the generator is d(x) where x NO ||a (l,, and is thus solely determined by ||a:]l2. With linear discriminator (x) = v œ, our minimax game becomes:
min max (fi(A,)) v) Ez-D [o' æ] - (E- [v [Az)]} AEROXA VER
(I)
Notice that when the activation Φ is an odd function, such as the tanh activation, the symmetric
property of the Gaussian distribution ensures that Ee / x]] = O, hence the linear discriminator in /i reveals no information about A" Therefore specifically for odd activations (or odd plus a constant activations), we instead use an adjusted rectified linear discriminator (x(x)) = R(x - C*)
to enforce some bias, where = (0(=) + <(-z)) for all æ, and R denotes the ReLU activation. Formally, slightly modify our loss function as:
(A v) = EnpD [o' R(x - C)] EE=NE(O)E (D (((((2)-C)))
(2)
We will show that we can learn each marginal of 'D if the activation function ø satisfies the following. Assumption 1. The activation function 6 satisfies either one of the following: 1. Φ is an odd function plus constant, and Φ is monotone increasing; The even component of db iee. 2 + z)), ), is positive and monotone increasing on x E oo).
Remark 1. All common activation functions like (Leaky) ReI.U, tanh or sigmoid function satisfy
Assumption 7
Lemma 1. Suppose A * O. Consider fi with activation that satisfies Assumption 2 and fi with activation that satisfies Assumption 1.. The stationary points of such fi and fi yield parameters A satisfying ||a:|| = | Il, Vi E [d].
To bound the capacity of the discriminator, similar to the Lipschitz constraint in WGAN, we regularize the discriminator. For the regularized formulation we have:
Theorem 1. In the same selting as Lemma !
alternating gradient descent-ascent with proper
learning rates on
min max (1i (A, |001//2]] or respectively A
min max (fi( -||/|111//2))
recovers A such that ||a:1l || Vi [d].
All the proofs of the paper can be found in the appendix. We show that all local min-max points in the sense of (Jin al., 2019) of the original problem are global min-max points and recover the correct norm of a,, Vi. Notice for the source data distribution æ = (I1, I2, ... ...))) ) ~ D with activation ø the marginal distribution of each x; follows 6(N(0, aa [|²)) and is determined by ||a,] |. Therefore we have learned the marginal distribution for each entry i. It remains to learn the joint distribution.
4 LEARNING THE JOINT DISTRIBUTION
In the previous section, we utilize a (rectified) linear discriminator, such that each coordinate v interacts with the i-th random variable. With the (rectified) linear discriminator, WGAN learns the correct ||a,]], for all However, since there's 's no interaction between different coordinates of the random vector, do not expect to learn the joint distribution with a linear discriminator.
To proceed, a natural idea is to use a quadratic discriminator (v := x T Vx = (xx T V) to enforce component interactions. Similar the previous section, study the regularized version:
1
min A VERaxa
max
(2(AA
3

---

Under review as a conference paper at ICLR 2020
where
fe(A.V) EEwDDV (o - E N0. Dv (v(()2))
(EEDD xx ] (x ((((A)))(A2) v).
By adding regularizer on V and explicitly maximizing over V:
1 2
g(A) max
[2(A,V)
V
B
xx
(E, [d(A TIl
2
In the next subsection, we first focus on analyzing the second-order stationary points of g, then we establish that gradient descent ascent converges to second-order stationary points of g.
4.1 GLOBAL CONVERGENCE FOR OPTIMIZING THE GENERATING PARAMETERS
We first assume that both A and 4 have unit row vectors, and then extend to general case since already know how to learn the row norms from Section To explicitly compute g(A), we rely on the property of Hermite polynomials. Since normalized Hermite polynomials {h. { forms an orthonomal basis in the functional space, we rewrite the activation function as ((x) E Jeh,, where is the i-th Hermite coefficient. We use the following claim:
Claim (eGe al. 2017 Claim 4.2). Let & be function from R. to R such that LR, e- and let its Hermite expansion be & = Ei= oyhs, Then, for any unit vectors u, v E IR,, we have that
(x= [Ø(uT ())((()))) T xx] = Σ of o)¹
Therefore we could compute the value of explicitly using the Hermite polynomial expansion:
f2(A Σ of (((AA))T)=-AAAA))))
Here X is the Hadamard power operation where (Xxi) = (X,x)* Therefore we have:
s(A) Σ of ((A"(A))T)'- (AAT)O))
We reparametrize with = AA and define ū(Z) = g(A) with individual component functions (2)(2) = { (E of ((2}x)* 2² Accordingly 25, = =ag, at) is the (j, k)-th component of the ground truth covariance matrix T
Assumption 2. The activation function o an odd function plus constant. In other words, its Hermite expunsion e E ozhy satisfies o, 0 for even i > 2. Additionally assume 0₁ + O. Remark 2. Common activations like tanh and sigmoid satisfy Assumption 2
Lemma 2. For activations including leaky ReLU and and functions satisfying Assumption 2 g(Z) has a unique stationary point where Z AA*)
Notice g(Z) Ej 0jk((2z) is separable across 2jk, where each 0j is a polynomial scalar function. Lemma comes from the fact that the only point for 0' is 2jæ 2jk- for odd activation é and leaky ReLU. Then we migrate this good property to the original problem we want to solve:
Problem 1. We optimize over function g when ||a)|| = 1,4i:
2
1
80
minA
g(A)
Σ of
((AT(A))T)oL (AA
s.1.
a a; 1,
4

---

Under review as a conference paper at ICLR 2020
Existing work Journée et al. (0008) connects ( to the optimization factorized version for g(4) (g(4)= = (AAA") )). Specifically, when d, all second-order stationary points for ((A) are first-order stationary points for (Z)). Though g is not convex,
able to show that its first-order
stationary points are global optima when the generator is sufficiently expressive, i.e, k 2 ko- In reality won't know the latent dimension ko, therefore we just choose k = d for simplicity. We make the following conclusion:
Theorem 2. For activations including leaky ReLU and functions satisfying Assumption 2 when k d, all second-order KKT points for problem Jare its global minimum. Therefore alternating projected gradient descent-ascent on Eqn. converges to A: AA (A")
The extension for non-unit vectors is straightforward, and we defer the analysis the Appendix.
FINITE SAMPLE ANALYSIS
Algorithm 1 Online stochastic gradient descent ascent on WGAN
1: Input: n training samples: œ1, 22,
... En, where each æ; ~ o(A*z), 2 ~ NO,, TExk), learning rate for generating parameters 77, number of iterations T.
2: Random initialize generating matrix (9).
3: for = 2,2, ... .T do
4: Generate m latent variables z1"
(1)
Zm ~ ~N( Taxk) for the generator. The empirical
function becomes
1 m
((Az, )o(Az!)) 1 Σ x T .v)
1 [v]2 1
F(D (A,V)
5: Gradient ascent on V with optimal step-size 1/ = 1:
v +- v(0 ny Vv fil), (A(t-1), v(t-1)).
6: Sample noise e uniformly from unit sphere
7:
Projected Gradient Descent on A, with constraints C (A((AAT) )a (A)A
1 <- Proje - (/( M() ( (A(t-1), vit) + e)).
8: end for
9:
Output: ( (ACO)T
In this section, we consider analyzing Algorithm [ i.c., gradient descent ascent on the following:
1
(AAz, )0(A2 ( 1
fuh (A,
V
2 III2
(4)
==1
Notice in each iteration, gradient ascent with step-size finds the optimal solution for V. By Danskin's 's theorem (Danskin 2012). our min-max optimization is essentially gradient descent over -(t)
E. x 1/3 with a batch of samples [=("),, i.e., stochastic gradient descent for (A) Ni,, (sE [0m,n (A)).
Im.n (A) maxy Jmm (A, V) =1l E. (Az, (o(2)))((()))))))))))))))))))(
Therefore to bound the difference between (n(A) and the population risk g(A), analyze the sample complexity required on the observation side (x; ~ D,i E [n]) and the mini-batch size required on the learning part (o(Az,), ), 2, (O, Ixxk).j E [m]). We will show that with large enough n, m, the algorithm specified in Algorithm that optimizes over the empirical risk will yield the ground truth covariance matrix with high probability.
Our proof sketch is roughly as follows:
With high probability, projected stochastic gradient descent finds a second order stationary point A of fa(+ as shown in Theorem 31 of (Ge et al. 2015).
5

---

Under review as a conference paper at ICLR 2020
2. For sufficiently large m, our empirieal objective, though biased estimator of the population risk 9(-), achieves good e-approximation to the population risk on both the gradient and Hessian (Lemmas 4 Therefore A is also an -pparxipoo second order stationary point (SOSP) for the population risk g(A).
We show that any e-SOPP À for ((4) yields an (cc)-firs order stationary point (FOSP) 2 ÁÄÄ for the semi-defnite programming on ū(Z) (Lemma
We show that any ((c)-FOSP of function g( induces most (cc) absolute error compared to the ground truth covariance matrix Z A* (A*) (Lemma 7).
5.1 OBSERVATION SAMPLE COMPLEXITY
For simplicity, we assume the activation and its gradient satisfy Lipschitz continuous, and let the Lipschitz constants be w.l.o.g.:
Assumption 3. Assume the activation 1-Lipschitz and 1-smooth.
To estimate observation sample complexity, we will bound the gradient and Hessian for the population risk and empirical risk on the observation samples:
((A)
1
B
[d(Az)o(A2) I] and
2
1
(n(A) =
N. (x-W(0,)exe) (=(A))((Az)
2
Claim 2.
Vg(A) Vgr (A) 2E, diag( (Az)) Xx)o(Az)z
where X- E D (xx)
( and Xn
- a, The directional derivative with arbitrary
direction B is:
DVg(A)[BI DV (A)[B]
=2E, diag( (Ax))
+ 2E [diag( @6 (Az) ( (A)
Lemma 3. Suppose the activation satisfies Assumption
Pr[l|X X,ll S [|||]] 2 1 - for
Odd/e log" (1)))
Lemma 4. Suppose the activation satisfies Assumption 2
With samples (d/e2 (1/6))
(V)((A) "gn(A)ll: < (cd|[A|l2) All2) with probability
5. Meanwhile, DVg
DV gm (A) I ((ed//2 B(l2) with probability
5.
5.2 BOUNDING MINI-BATCHI SIZE
Normally for empirical risk for supervised learning, the mini-batch size be arbitrarily small since the estimator of the gradient is unbiased. However in the WGAN setting, notice for each iteration, randomly sample batch of random variables {z:) and obtain gradient of
in Algorithm However, the finite sum is inside the Frobenius norm and the gradient on each mini-batch may no longer be an unbiased estimator for our target ga || Σ a E- [<(A))(Azz)]]
n (A) 1 A.Ei,aa
a. ΣT ol ((Az))0(A)))
In other words, conduct stochastic gradient descent the function f(A) = Ezōm, n (A). Therefore we just need to analyze the gradient error between this fA4 and 9r, (A) (i.e. 9m. is almost an unbiased estimator of g.). Finally with the concentration bound derived in last section, we get the error bound between ((A) and ((A).
Lemma 5. The empirical risk Jm,n is almost unbiased estimator of In. Specifically, the expected function f(A) = (0, (.EE [mm..] satisfies:
(V)(A) -9. (A)]l S 0 11
2 hides log factors of for simplicity.

---

Under review as a conference paper at ICLR 2020
For arbitrary direction matrix B.
S =1
In summary, we conduct concentration bound over the observation samples and mini- sizes, and show the gradient of f(A) that Algorithm i optimizing over has close gradient and Hessian with the population risk ((A). Therefore a second-order stationary point (SOSP) for f(A) (that our algorithm guaranteed to achieve) is also an approximated SOSP for g(A). Next we show such a point also yield an approximated first-order stationary point of the reparametrized function g(Z) = (A),, VZ AAT.
5.3
RELATION ON APPROXIMATE OPTIMALITY
In this section, we establish the relationship between and g. We present the general form of our target Problem
AERCER
g(A) -((AA)
(5)
(xAA) = Yr: X; E S, E R- 1,
Similar to the previous section, the stationary property might not be obvious on the original problem. Instead, we could look the re-parametrized version as:
minzes
g(Z)
(6)
s.t.
Tr Tr(X,Z) = ys E z 0,
Definition 1. matrix E Ra is called an e-approximate second-order stationary point (c-SOSP)
of Eqn. (5) if there exists a vector À such that:
Tr X,A) ye é E [n] II ((VZ)(AAT) E Tr(B DV A(( -c
{ā,] span the column space of
BB s.t. Tr(B X,A) =0
Here ((A, A) the Lagrangian form -(AAT)- E A X,A) -:))
Specifically, when e = 0 the above definition exactly the second-order KKT condition for optimiz- ing (5) Next present the approximate first-order KKT condition for (6):
Definition 2. symmetric matrix 8" is an e-upproximate first order stationary point function
(e-FOSP) if and only if there exist a vector E I and symmetric matrix S E S such that the
following holds:
Tr(X;2) = Vs.i E [n]
Z 2 0,
$ > -el,
|Sā I &
{āj}s span the column space of Z
S= V=Vz((Z)
Di=1o;X,
Lemma 6. Let latent dimension to = For an e-SOSP function with and X, it infers an
c-FOSP of function (6) with Z, and that satisfies: Z = AA X and S Zzū(AA))
N.X,
Now it remains to show an e-FOSP of ā(2) indeed yields good approximation for the ground truth parameter matrix.
Lemma 7. If is an c-FOSP of function 6 then I| - 1' < O(c). Here z = (A*) is the optimal solution for function 6
Together with the previous arguments, we finally achieve our main theorem on connecting the recovery guarantees with the sample complexity and batch size
Theorem 3. For arbitrary 8 < 1, given small enough learning rate 1) < 1/poly(d, log(1 1/8). let sample size n Z ( log (1/6)), batch size m 2 Old /e). for large enough T=poly(1/m)) 1/c, d, (og(1/)), the output of Algorithm satisfies (TA
11 - O(e)
with probability 6, under Assumptions 3 and d.
'The exact bound comes from the fact that when diagonal terms of AAT fixed, ||A||2 O(va).
7

---

Under review as a conference paper at ICLR 2020
Sarth
Sigmole
6.10
0.000
0.29
0.000
Figure Recovery emoor (IAA =²1l=) with different observed sample sizes n and output dimension d.
SIMULATIONS
In this section, we provide simple experimental results to validate the performance of stochastic gradient descent ascent and provide experimental support for our theory.
We focus Algorithm [ that targets to recover the parameter matrix. We conduct thorough empirical studies on three joint factors that might affect the performance: the number observed samples (we set function o, and the output dimension d. Figure [ we plot the relative error for parameter estimation decrease the increasing sample complexity. We fix the hidden dimension &t 2, and vary the output dimension over {3, 5, 7) and sample complexity over (500, 1000, 2000, 5000, 10000). Reported values averaged from 20 runs and show the standard deviation with the corresponding colored shadow. Clearly the recovery error decreases with higher sample complexity and smaller output dimension.
as in general GAN training algorithms), the different choices of activation
1.0
1.00
0.5
(2468)
InC (36
166-9.71
-3.50
-1.0
-1.00
-0.75
-050
-335
0.60
-1.00 -2.76
-2.0
-2.0
0.00
0..5
0.50
0.7
3.00
(a) leaky ReLU activation 0.2)
(b) tanh activation
Figure 2: Comparisons of different performance with leakyReLU and tanh activations. Same color starts from the same starting point. For both cases, parameters always converge to true covariance matrix. Each arrow indicates the progress of 500 iteration steps.
To visually demonstrate the learning process, we also include a simple comparison for different d: i.e. leaky ReLU and tanh activations, when 1 and d = 2. We set the ground truth covariance matrix be [1, 1; 1]. and therefore a valid result should be [1, 1] or [1,, 1]. From Figure we we could see that for both leaky ReLU and tanh, the stochastic gradient descent ascent performs similarly with exact recovery of the ground truth parameters.
7 CONCLUSION
We analyze the convergence of stochastic gradient descent ascent for Wasserstein GAN learning single layer generator network. We show that stochastic gradient descent ascent algorithm attains the global min-max point, and provably recovers the parameters of the network with absolute error measured in Frobenius norm, from @ /c²) i.i.d samples.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 214 223, 2017.
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (GANs). In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 224 232..2. JMLR. org, 2017.
Sanjeev Arora, Andrej Risteski, and Yi Zhang. Do GANs learn the distribution? some theory and empirics. 2018.
Yu Bai, Tengyu Ma, and Andrej Risteski. Approximability of discriminators implies diversity in GANs. arXiv preprint arXiv: 10586, 2018.
Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using generative models. In Proceedings of the 34th International Conference on Machine Learning-Volnn Voluue 70, pp. 537-546. JMLR. org, 2017.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view expressivity. In Advances In Neural Information Processing Systems, pp. 2253-2261, 2016.
John M Danskin. The theory of max-min and its application to weapons allocation problems, volume 5. Springer Science Business Media, 2012.
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. arXiv preprint 180. 04252,, 2018a.
Constantinos Daskalakis and loannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems, pp. 9236-9246.
2018b.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint arXiv: 171100/711.00444: 1.00141, 2017.
Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis. Efficient statistics, in high dimensions, from truncated samples. In the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2018.
Vincent Dumoulin, Ishmael Belghazi. Ben Poole, Olivier Mastropietro, Alex Lamb, Martin Arjovsky, and Aaron Courville. Adversarially learned inference. arXiv preprint arXiv:1606.00700 2016.
Soheil Feizi, Farzan Farnia, Tony Ginart, and David Tse. Understanding GANs: the LQQ setting. arXiv preprint arXiv: 1wX.h:1710.10990 2017.
Rong Ge, Furong Huang. Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. In Conference on Learning Theory, pp. 797-842, 2015.
Rong Ge, Jason Lee, and Tengyu Ma. Learning pee-hidden-layer neural networks with landscape design. arXiv preprint 1rXiv:1711.005000 2017.
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Simon Lacoste-Julien, and loannis Mitliagkas. Negative momentum for improved game dynamics. In the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
Ian Goodfellow, Jean Pbudet-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural informa- fion processing systems, pp. 2672-2680, 2014.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. In Advances in neural information processing systems, pp. 5767-5777, 2017.

---

Under review as a conference paper at ICLR 2020
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to a local nash equilibrium. Advances in Neural Information Processing Systems, pp. 6626-66333 2017.
Phillip Isola, Jun-Yan Zhu, Tinghui Zhou, and Alexei A Efros. Image-to-image translation with conditional adversarial networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1125-11344 2017.
Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Minmax optimization: Stable limit points of gradient descent ascent are locally optimal. arXiv preprini
2019.
Michel Jourée,, Francis Bach, P-A Absil, and Rodolphe Sepulchre. Low-rank optimization for semidefinite convex problems. arXiv preprint arXiv:0807.4423, 2008.
Christian Ledig, Lucas Theis, Ferene Huszár, Jose Caballero. Andrew Cunningham, Alejandro Acosta, Andrew Aitken, Alykhan Tejani, Johannes Totz, Zehan Wang, et al. Photo-realistic single image super-resolution using generative adversarial network. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4681 46900, 2017.
Tengyuan Liang. how well generative adversarial networks learn densities: Nonparametric and parametric results. arXiv preprint arX1v:1811.03179, 2018.
Tengyuan Liang and James Stokes. Interaction matters: A note non-asymptotic local convergence of generative adversarial networks. In the 22nd International Conference on Artificial Intelligence and Stafistics AISTATS), 2019.
Tianyi Lin, Chi Jin, and Michael Jordan. minimax problems. arXiv preprint arXiv:1906.003: 2019.
On gradient descent ascent for nonconvex-come concavve
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of gans. In Advances in Neural Information Processing Systems, pp. 1825-1835, 2017.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for GANs do actually converge? arXiv preprint arXiv:/801 3xXiv:/801.04000 04406, 2018.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. arXiv preprint urXiv:/901.085. 2019.
Vaishnavh Nagarajan and Zico Kolter. Gradient descent GAN optimization is locally stable. In Advances in Neural Information Processing Systems, pp. 5585-5595, 2017.
Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell. Adversarial discriminative domain adaptation. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 7167-7176, 2017.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Shanshan Wu, Alexandros G Dimakis, and Sujay Sanghavi. Learning distributions generated by one-layer relu networks. arXiv preprint 1909v01909.01880 2019.
Pengchuan Zhang, Qiang Liu, Dengyong Zhou, Tao Xu, and Xiaodong He. On the discrimination- generalization tradeoff in gans. 2018.
10

---

Under review as a conference paper at ICLR 2020
A OMITTED PROOF FOR LEARNING THE DISTRIBUTION
A.1 STATIONARY POINT FOR MATCHING FIRST MOMENT
Proof of Lemma / To start with, consider odd-plus-constann monotone increasing activations. Notice that by proposing a rectified linear discriminator, we have essentially modified the activation function as Φ = R( C), where C {d((z) + <(-x)) is the constant bias term of Φ. Observe that we can rewrite the objective f1 for this case as follows:
(A v) 1= Ing x "(AA2) Eo. ((Az).
Moreover, notice that Ø is positive and increasing its support which is [0, +o0).
Now let us consider the other case our statement where @ has a positive and monotone increasing component in [0, +00). In this case, let us take:
x(x) = -
x 20
O.W.
Because of the symmetry of the Gaussian distribution, we can rewrite the objective function for this case as follows:
(A V0= TT(AA ((A"=)) V(,, (()(z)
Moreover, notice that ē positive and increasing on its support which is [0, +20).
To conclude, in both cases, the optimization objective can be written as follows, where & satisfies Assumption 2 and is only non-zero on [0, +00).
(A, v) Ez-N((0 Io xig "(AA2)) Ez-N(0,)exa ((Az).
The stationary points of the above objective satisfy:
V Vifi v) Ez-N( ((A²)) EonNNO.
Va, (A = - EE- -E. (2 z)2 =0. 0.
We focus on the gradient over u. To achieve (A, = 0, the stationary point satisfies:
Vj, Ex, xn (8((() 2) )(a (a]]2) 2). i.e.
Vj, Vi..Ee..ooo.leespppdd0
1P)))
To recap, for activations & that follow Assumption in both cases we have written the necessary condition stationary point to be Eqn. 7. where ø is defined differently for odd or non-odd activations, but in both cases positive and monotone increasing on support [0, oo). We then argue the only solution for Eqn. 7 satisfies ||a;] ||a]]|, Vj. This follows directly from the following claim:
The function h((a) := E f(x)) > 0 is monotone increasing function if f is positive and monotone increasing on its support [0, oo).
Claim 3.
We could see from Claim that the LHS and RHS of Eqn. 7 simply h([la,]) and h([la)]]) for each j. Now that h is an monotone increasing function, the unique solution for h( [a, h((aa)))) match the norm: ||a, ||a ||, Vj.
Proof of Claim
h(())
= Ex-N(0.02) =
[ f(x)e- f de
aflay)e 4dy E (o.oo.)))(oo))).
11

---

Under review as a conference paper at ICLR 2020
Notice (a) = (o.)) (oz) + f(zz)]. Since f. f', and a >> 0, and only care about the support of f where is also positive, therefore //' is always positive and h is monotone increasing. 17
To sum up, stationary point where Vfi v) have
Vi. |
||a.||-
A.2 PROOF OF THEOREM 1
Proof of Theorem L We will take optimal gradient ascent steps with learning rate 1 on the discrimi- nator side v, hence the function we will actually be optimizing over becomes (using the notation for á from section A.1):
(AA) max fi = 1 100 O(A - E
We just want to verify that there's spurious local minimum for h(A). Notice there's no interaction between each row vector of A. Therefore we instead look at each h4 == 1 (EE-N(0..homm (acaaaon)o((())))))))))))))) p(((a))z)) Ez-Nii,texe [)) for each i. Now Vh,(a;)
- (Ez-N (((aa) T 2) xo =)) ( (1== symmetry of the Gaussian, take a; aen where ||a:|]. is easy to that checking whether 1 2 (a = equivalent to checking whether =1 =
z)). Due to the
Recall that δ is supported on [0, +oo) and it is monotonically increasing on its support. Hence, 1=,-~((,1)210'' (az1) 0 unless 0. Hence, suppose ||a:|l + 0, vi. Then Vah(A) iff M(A) 0, i.e. Eg ko) /
(0
Therefore all stationary points of h(A) global minima where E2-N(0., ,0(A2)) Bx-N((.eexx)(Az)) and according to Lemma this only happens when ||a,]| = ||a; vi [d]. O
A.3 STATIONARY POINTS FOR WGAN WITH QUADRATIC DISCRIMINATOR
Proof of Lemma 2 To study the stationary point for ğ(Z) Eşh I5x (2jx), we look at individual
(2)(2) = 3 ( ((
Notice for odd-plus-constant activations, is zero for even > 0. Recall our assumption in Lemma also requires that 01 * Since the analysis is invariance to the position of the matrix Z. we simplity the notation here and essentially want to study the stationary point for f(a) = EE of (a' -b²) for some constant b and oi, where 0 *
f((a)
oilla' - bb)
Σ
iofa'-1 odd
oodd
a 12
(a b) of Σ
of Σ
iofa'-1
123 oild
13
= (a (a--b)00 (II
Notice now f((a) = 0 + = b. This is because the polynomial (a( is factorized to - b and two a'-b' to denote Σ3000 abbi-j, which is
factors and that are always positive. Notice here we use a-b always nonnegative. This is simply because a² - b² always shares the same sign as b when is odd. Therefore I=o + Ei odd a-b > 0, Va.
2
*The component has heen cancelled out.
12

---

Under review as a conference paper at ICLR 2020
Meanwhile, since a²-1 is always nonnegative for each odd i, we have II= of + +.+EEs Li33 odd 20,0'-1 is also always positive for any
Next, for activation like ReLU, loss 0)イ(2) cos (or)) (x)))) (Daniely al. 2016). Therefore 11(-1) 0 for any zjk- This fact prevents from getting the same conclusion for ReLU.
where h(z) = ( - x² +22+0 (TT
However, for leaky ReLU with coefficient of leakage (0,1), Φ(z) max(x, ax) (1 a) a)RLL(z)) + ar.
We have
Ez- lo(a, ( x)] =(1 - ReLUU 2 ReLU 2) (1 ReU
+ (1 - a ZReLU(a +)+ a²²Baa za,²
=(1 -
a1- h
a₂) + aa, aj
Therefore for leaky ReLU (=)(=) = (1- (()) a(= -=xx)² and [3x(z) = ((1 (L==))(())) ( for all and (z)(2) + 22
Now with a > 0, a +a
To up, for odd activations and leaky ReLU, since each (z)(2) only has stationary point of 2jk- the stationary point Z of ((Z) Σ5x Oyk also satisfy Z Z -A*)
Proof of Theorem 2 Instead of directly looking at the second-order stationary point of Problem) look the following problem its reparametrized version:
Problem 2.
2
minz z
Ø(Z) Σo3 of ((z)) 200)
s.t.
24 = vi.
Z Z
Here 7" (A*) and satisfies z 1, Vi.
Compared to function g in the original problem | satisfies that @(AAT) g(A).
A matrix Z satisfies the first-order stationary point for Problem 2 if there exists a vector such that:
24 = 1,
Z 0.
S z 0,
S7 00
S Vzg(Z) - diag(a).
13

---

Under review as a conference paper at ICLR 2020
Therefore for stationary point Z, since Z" = AA(AA"T 0, and S = 0. we have (S, 2" Z) (S, - 2 0. Mcanwhile,
(Z' Z,5)
=("" Z, Vzf(Z) - -dag(o))
=(" - Z. v2f(Z))
(diag(Z" - 2)
- (+) - 2y)0b/
Σ (zy 2 P(as) ziz)
(Refer to proof of Lemma for the value of g')
Σ (zij 2 P(zi))
8j
<
(P is always positive)
Therefore 2 z) = 0, and this only happens when Z
Finally, from Journée et al. (2008) we know that any first-order stationary point for Problem second-order stationary point for our original problem 1
Therefore we conclude that
second-order stationary point for Problem | are global minimum A: AA AA*)
A.4 LANDSCAPE ANALYSIS FOR NON-UNIT GENERATING VECTORS
In the previous argument, we simply assume that the norm of each generating vectors a, to be 1. This practice simplifies the computation but is not practical. Since first, we could analyze the landscape of our loss function for general matrix A.
able to estimate ||a;]| for all i
The main tool is to the multiplication theorem of Hermite functions:
L3 Σ
1)(()
(2i)1 2
(x) = hn(a)) =
a n- (a² 1) 0
2-hh, (2
2i i!
For the ease of notation, denote the coefficient v/ n~2 1)x the calculations for Hermite inner product for non-standard distributions.
(20) (201 2- We extend
Lemma 8. Let (x. y) be normal variables that follow joint distribution N(0 [la?, aBp) [a:3p, (8]) Then,
E14 mla 2- if = n (mod? 2)
Eh (x)nn(y)
(8)
O.W.
Here 1 min(m,n..
'Throughout analysis low rank optimization in Journée al, (0008), they require function g(Z) to be convex. However, by carefully scrutinizing the proof, one could see that this condition is not required in building the connection of first-order and second-org -rder stationary points of (AA) and g(2). For more cautious readers. we also show relaxed version in the next section, where the equivalence of SOSP of g and FOSP of is special of it.
14

---

Under review as a conference paper at ICLR 2020
Proof. Denote the normalized variables f z/a, v/ Let I = min n).
El (x)) (v))
= El (o)
T 121
na
i=
1 1
Tl 1133 6(m
m.
(n 200-2)00---
(Lemma ??)
i=0 j=0
L Σ
nh
1 p
if m = n (mod 2)
O.W.
Now the population risk becomes
g(A)
EEND [x
]]
E (O. [0(Az)((Az)
2) (la 2)o(a} z)
Σ (z.()
2
To simplify the notation, for a specific i, pair, we write + 2/0; a = ||a:]l and ÿ = a, 2/3, where 8=1 ==] Namely we have (#, 0) NO, [[,, p): [p. I]]). where p cos(a;, az). Again, recall ((a²) D k odd (ahi(ax)) Ex edd (t).
E 10
Σ Li odd
am am t (i)
Eonh(())
Σ
Tm E ha (1)
m,n
Σ
Σ
n.k n.k fg p p=-2k 2k
m odd
T odd
k=
Therefore we could write out explicitly the coefficient for each term / k odd, as: C
Σnzk odd Jn
73 (Emzn Jm). We have (iy()1)) (Ex odd cuely - E. ods ex (2 )22
Now suppose to have the same sign, and |ay || 2 1, V or ||as|| I 1, Vi, each coefficient 2 0.
Therefore still the only stationary point for g( Z
B OMITTED PROOFS FOR SAMPLE COMPLEXITY
B. OMITTED PROOFS FOR RELATION ON APPROXIMATE STATIONARY POINTS
Proof of Lemma 6
We first review what we want to prove. For a matrix A that satisfies e-approximate
SOSP for Eqn. we define SA- Vzğ(AAT) >" XxX;. The conditions ensure that A, X, SA satisfy:
Tr(AT Vi, || 5 <<(āā.l2,
(āz) )j span the column space of (9)
Tr(B AAAA A)B)) 2 B
vB s.t. Tr(BT X,A) = 0.
15

---

Under review as a conference paper at ICLR 2020
0 We just want show Z == , X, and S == SA satisfies the conditions for c-FOSP of Eqn. (6). Therefore, by going over the conditions, its easy to tell that all other conditions automatically apply and it remains to show A -cl
By noting that VAC(A, A) = AA, one has:
Tr(B D. (AA AV
2
=Tr(B' BBB) Tr DA ZAVz)(AA))BAA Σ DAN,BB)T((B X,A)
(from Lemma 5 of Journée et al (2008)
=Tr(B" SAB) TM DAV (AAz
(10)
(From Eqn. we have Tr(B" X,A) 0)
Notice that Rdxk and we have chosen d for simplicity. We first argue when is rank- deficient, i.e. rank(A) < k. There exists some vector e E I such that Av = O. Now for any vector E RRd let B by Therefore AB = Aub T From (10) we further have:
1 DAV DAVI"DAAAAAAA)
2
Tr(B" SAB) Tr(AB DAVzū(AA
Tr(ub' SAbe ) = | SAb
2 B12
(from (
-=//2[u1|(1bTT]
Therefore from the last three rows we have SAb 2 bl/ for any i.. SA h ee/2laxd- On the other hand, when A is full rank, the column space of A is the entire HR vector space, and therefore SA Z -cTaxe directly follows from the second line of the c-SOSP definition.
B.2 DETAILED CALCULATIONS
Recall the population risk
((A) EE xx Ex,, [d(Az)o(Az) T]
Write the empirical risk on observations as:
12
9a(A) = 1 "
Σ x B2-N((.)exx) [o(A=)o(Az)]
2
Claim 4.
Vg(A) - (A) = 2E (diag(d (Ax))) -x)
where X = EEwDDDDu xxx T. and Xn, = - TT
Proof.
Vg(A) (g) v(g(A) (n())
v (X - XX, + Xn, 21 (d(A2)((A2) (AA
=V (X, X.B.ee((.eeee) (+(A)))(A2)T)
Now write S(A) = ((Az)((A2))
[S(A + AA) S(A));
=o(aā x + da; 2)<(a} z + Daj o(a 2){{{
=d' A) zΦ(a} 2) + (aa,, 2) zo(a, 2) 0(1A4113
16

---

Under review as a conference paper at ICLR 2020
Therefore
[S(A+ + AA) - S(A),;
= (a, a) zo(Az) + (Ax) AAz) 2) + O[|AA||?)
Therefore
S(A+ AA) - S(A) = (42)) + *((z)> AA diag( ((ag()(AAz)), (11)
And
9 + AA) (A - AA) (o(A) - 9n
(X,, E, [S(A + AA) S(AA))
=E, - X, diag( @6 (Az) A AZ) - 0(Az)z T AA diag(ø' (Az))
222,,(iaae ø' (Az) (X,, X))(Az)> AAA..
Finally we have Vg(A) Vg. 2EE [diag] (Ø' (Az)) - -X)(A2)==]]
Claim 5. For arbitrary matrix B, the directional derivative of Vg(A) gn with direction B
is:
DA -
2E, [diaglo' diiaglo(Az))(xx) (Az)) - X))o (Az) XA)( (Bz)z + [diag( (Azz) (Bz))
X)0(A2)=
Proof.
g(A + tB)
=2 (diag( ('x (Bz)) - (B
=2E, diag(('(A22) t(Bz) 8 (Xx - to O
Therefore
g + tB) - 9(A)
lim
2 [diag( @ (Ax))(Xn, - ()) (B) =]=
+ 2E ddagg (0" (Az) o (B2)) - -X)(A2)>
B.3 OMITTED PROOFS FOR OBSERVATION SAMPLE COMPLEXITY
Proof of Lemma 3 For each æ; o(Az.) 2; N(0, TRK)). Each coordinate [
[o(a) 2:) < aa zil since & is 1-Lipschitz. Without loss of generality assumed |ay] Vj
therefore a) z ~ (o, Ixxx). For all i [m].j E [d] | S log(nd/)) with probability
Then by matrix concentration inequality ((Vershynin, 2010) Corollary 5.52), we have with probability 1-8: (1-))X = X, = (1+c)X if 2 (2d/e2 log (nd/5)). Therefore set n @dd/c² (odde2log@1 (og2(1/5))
will suffice.
Proof of Lemma
X1J Ez-vio.nxu 2))(a] 2)
{ { i=j
itj
Forr simplicity, we analyze if ((0) O w.o.lgg throughout this section, since the bias term is canceled in the observation side with of 6("2z) and the learning side with (AAz).
17

---

Under review as a conference paper at ICLR 2020
Therefore | 2. Together with Lemma 3 |X - X, x S w.p 1 6. Recall
(g(A) Vgn (A) 2E, [daag(0' (diag("(Az)) - X,)x(Az)=
2E, G(z).
where G(z) is defined as diag( (X -x,))xX)xx)((( (Az)) T. We have ||G(z)] - [|A||[]|||XXX]]
[[Vg(A) Vgn(1)ll:
[|[=[[((>]]I
< 2|E
- 2E ||= X
< 2|| 2 Bz 1|11=1
= A|kd 2
For the directional derivative, we make the concentration bound in similar way. Denote
D(z) =
- x) (Azz) o (Bz)z + diag(o" (Az) (Bz)) - x))(Az)=
[= < I B| || (1 + |+]]||]).
Therefore (} - A V 9m (A)[ < ( ||||| with probability 1- 8.
B.4
OMITTED PROOFS ON BOUNDING MINI-BATCH SIZE
Recall
Im,n (A) =
(Azz))(Azz)
2
1=1
j=1
Write S,(A) = ((Az))0(AZ))
Then we have
(m, =
Xn
(A),
Σ S5(1)
2
j=1
1
Σ
(S,(A), Sy(A)
Σ
m
- 111
+
2m
On the other hand, our target function is:
(A) =
x T - -E-N((o, [0(A))0(Az]
2
||E [ST1 (Bs[S), X.,) + 2 ||x,117
2
Therefore Esğm,n(A)) - 9n (A) = 1 (Es| (()))()))
24m
Claim 6.
VEssm,. (g))))) 2 E, [diag(o' (d((4d)))(()))((A)) -die((((4)))3/5554)))4444))
m
Proof.
(VEggm, Vgn: AA)
-Esğm, A AA) gn (A + AA) (Esâ + 9, (4) +A())
(s][S(AAAA]]) [s|()(A) |E - A 1|00::4---000------000----------
|E + O(IAA13)
2m
1 (( 5(A) (Es(((A)), ((4))))()()(((())))))5555.5 Fs(S(A AA) 5(A)) O(IAA|1)
m
1
diag(())))aa)) (i(Gs)))) (Es(()))))))))())))))_ E. (idgg( (Az=)))) (444544)))BBguae(((((4444A4333 E,
+ ((IAA|)))
(from Eqn. and symmetry S)
2
=(
Ez [diag( (diag(('(u (A2))) -
AΛ) + O(IAA||3)
18

---

Under review as a conference paper at ICLR 2020
Similarly to the derivation the previous subsection, we again derive the bias in the directional derivative:
Claim 7. For arbitrary matrix direction B,
DAVESom (A)[B) DA P. (A)
2 x [diag( (B2)) (EgE()) m
+ diag( (Ax)) (B2)) E- (Bz))o(Az) d(Ax)= (Bz))
diag(d (A))) (d)))) (Bz))
) 1) d(Az)=
+ diag( (Az)) ( - ()) (Az) o (Bz)))²
B.5 OMITTED PROOF OF THE MAIN THEOREM
Proof of Lemma 7 On one hand, suppose Z is e-FOSP property of g in (6) along with the matrix and vector o, we have:
(Vg(Z), 7 7%)
-8, Z*)
(since Z - Z has 0 diagonal entries)
<|) (Z 7
(T is the tangent cone of PSD matrices at Z)
[|12|2 -
m Sā, }1 1'
(āj is the basis of the column space of Z
< 7 z-
(12)
(from the definition of c-FOSP)
On the other hand, from the definition of g. we have:
LZ - Z", Vğ(2))
Σ (2ig 21g (,y)),(()))
1j
(Zig =2g)² Σ
Pa((())))
Σ
1j
k oudd
à odd
2 7"
1
(13)
Here polynomial (x(y)) = (2/)
(2t / 2²) is always positive for * 2" and l to be odd.
Therefore by comparing 12) and 13 we have Z 10 I1 2 13 i.c. 1| Z -0 Oce).
Proof of Theorem From Theorem 31 from Ge al. 2015), we know for small enough learning rate 17, and arbitrary small there exists large enough 7 such that [ generates an output
A() that is sufficiently close to the second order stationary point for f. Or formally we have,
Tr((A X,A Wis (A Ei Ax slll <emin |Agll
Vj E k)
Ti(B DA ALy A)(B) 2 - BIB
YB, s.t. Tr B X,A) =0
(A, S(A) Σd (T y:). Let (ā: = A form the basis of the
column vector space of A(T), Then the second line is a sufficient condition for the following: | (VA)(A(T)) Ei=1 (x)))ll I e, Vj E [k].
19

---

Under review as a conference paper at ICLR 2020
Now with the concentration bound from Lemma 5 suppose our batch size m 2 O(d' /c), we have ||V Ag. (A(T) - Vlf(A())llz I and || V A9, (A()) DA
B|l
for arbitrary B. Therefore again we get:
T | (V (VAg E =1 (rx 2 26,
=
Vj [k] Tr(B DAV.DAVAA A.. (A {) 2 B1e &.l. 8. Tr(B' X;A) -0
Next we turn to the concentration bound from Lemma 4 Suppose we have when the sample size
2 Old fca log" (0g8)) || [B] - DA V A9. (A)[Bll S Ocll and V[
Vgn A)]l2 S ((e) with probability 6. Therefore similarly we get A is an ((c)-SOSP for
((A) = DE= of ())) (AA ) [|
Now with Lemma 6 that connects the approximate stationary points, we have == A is
also an e-FOSP of j(Z) E o3 (( l|
Finally with Lemma 7 we get || - 1 - O(c).
20


Reviews:
[{"review_id": "HJgk6-WCFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "I have read the authors response. In the response the authors clarified the contributions of this paper. I agree with the authors that the analysis of gradient descent-ascent is a difficult problem, and the optimization results given in this paper is a contribution of importance. Because of this I have improved my score.\n\nHowever, I do not agree with the authors that studying quadratic discriminators instead of more complicated ones should be considered as a contribution instead of drawback. In my opinion, as long as the focus is on WGAN, results involving standard neural networks are still more desired compared with the results in this submission. For example, similar results for a neural network discriminator might be even more impactful, because the optimization problem is even more difficult. Therefore I still consider the simple discriminator and generator as a weak point of this paper.\n\n\n======================================================================================================\n\nThis paper studies the training of WGANs with stochastic gradient descent. The authors show that for one-layer generator network and quadratic discriminator, if the target distribution is modeled by a teacher network same as the generator, then stochastic gradient descent-ascent can learn this target distribution in polynomial time. The authors also provide sample complexity results.\n\nThe paper is well-written and the theoretical analysis seems to be valid and complete. However, I think the WGANs studied in this paper are simplified too much that the analysis can no longer capture the true nature of WGAN training. \n\nFirst, the paper only studies linear and quadratic discriminators. This is not very consistent with the original intuition of WGAN, which is to use the worst Lipschitz continuous neural network to approximate the worst function in the set of all Lipschitz continuous functions in the definition of Wasserstein distance. When the discriminator is as simple as linear or quadratic functions, there is pretty much no “Wasserstein” in the optimization problem.\n\nMoreover, the claim that SGD learns one-layer networks can be very misleading. In fact what is a “one-layer” neural network?\n- if the authors meant “two-layer network” or “single hidden layer network”, then this is not true. Because as far as I can tell, the model $x = B \\phi(A z)$ is much more difficult than the model $x = \\phi(A z)$. The former is a standard single hidden layer network which is non-convex, while the latter is essentially a linear model especially when \\phi is known.\n- if the authors meant “a linear model with elementwise monotonic transform”, then I would like to suggest that a more appropriate name should be used to avoid unnecessary confusion.\n\nAs previously mentioned, the discriminators are too simple to approximate the Wasserstein distance, and therefore in general it should not be possible to guarantee recovery of the true data distribution. However, in this paper it is still shown that certain true distributions can be learned. This is due to the extremely simplified true model. In fact, even if the activation function $\\phi$ is unknown, it seems that one can still learn $A^* (A^*)^\\top$ well (for example, by Kendall’s tau).\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Byl5lg8TKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 attempt to prove that the Stochastic Gradient Descent-Ascent could converge to a global solution to the min-max problem of WGAN, in the setting of a one-layer generator and simple discriminator. They also show that the linear discriminator could be used to learn the marginal distributions of each coordinate, while a quadratic one could obtain joint distributions of every two coordinates. Since the linear discriminator and the quadratic one could be solved in one step Gradient Ascent, the author applied the standard analysis method to reveal the property of the Gradient Descent method. Experiments are also carried out to justify their theory that the WGAN could recover the distribution.\n\nHowever, the most significant drawback of this paper is that the settings for the discriminator are too simple, which leads to the following two problems: 1) Revealing the joint distributions of two coordinates is still much weaker than the desired result of recovering the true distribution of the data. 2) The analysis of this paper could not be extended to a complex discriminator since it would be suffered from the training error propagation in the Gradient Ascent step, instead of getting an accurate solution for the Gradient Ascent step. \n\nTherefore, more explanations are desired to be given to bound the error propagation and what will the complimentary discriminator learn from the data distribution.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1xjCMHAtr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "The authors provide a long text to justify their contributions and I have read it thoroughly. Unfortunately, I find the responses don't really address my concerns.\n\nMy major concern is that I cannot understand how quadratic discriminator can be treated as WGAN. The authors replied that the regularization considered in the paper might be treated as Lipschitz constraint for bounded data sets. However, the data sets can’t be bounded because in the paper, the authors consider a special case where the data sets generated from a teacher network where the input is Gaussian noise. Moreover, the authors said that they would add an explanation of this important point in the revision but I haven’t found any revision yet.\n\nMy another concern is that why the authors don’t study the two layer network discriminator. The authors replied that the choice of discriminator is designed in tandem with the choice of generator.  If they use a standard two layer ReLU network as discriminator, this would hurt the sample complexity. I partly agree with that it will be nice if we can design a better discriminator according to the different choice of generator. However, it will be more convincing to show the convergence of WGAN if the authors consider NN discriminator rather than quadratic discriminator which hardly be used in GAN.\n\n==================================================================================================\nI found this paper over claims its contribution a lot, which is quite misleading. The title of this work is SGD LEARNS ONE-LAYER NETWORKS IN WGANS. And the authors claim that they analyze the convergence of stochastic gradient descent ascent for Wasserstein GAN on learning a single layer generator network. But actually this paper only considers two kinds of simplified discriminators: a (rectified) linear discriminator and quadratic discriminator, which are very different from WGAN used in practice. The analysis of two special cases are hard to be extended to the analysis of WGAN and thus can hardly help to explain why WGAN is successfully trained by SGD in practice.\n\nIn section 3, the authors consider the rectified linear discriminator, which is quite similar to the standard two layer network with relu activation but the first layer is fixed. The authors prove that the generator can learn the marginal distribution but may not learn the joint distribution. In the beginning of section 4, the authors explain that this is because there is no interaction between different coordinates of the random vector. To learn joint distribution, the authors extend the linear discriminator to the quadratic discriminator and think of it as a natural idea.\n\nFor the rectified linear discriminator, the regularization of the discriminator is the norm the output layer of discriminator which can be related to the Lipschitz constraint in WGAN. But for quadratic discriminator, I cannot understand how this setting can be treated as WGAN without further explanation from the authors.\n\nI wonder why this work doesn’t consider the standard two layer network discriminator which also has the interaction between different coordinates in the first layer.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This article studies convergence of WGAN training using SGD and generators of the form $\phi(Ax)$, with results on convergence with polynomial time and sample complexity under the assumption that the target distribution can be expressed by this type of generator. This expands previous work that considered linear generators. An important point of discussion was the choice of the discriminator as a linear or quadratic function. The authors' responses clarified some of the initial criticism, and the scores improved slightly. Following the discussion, the reviewers agreed that the problem being studied is a difficult one and that the paper makes some important contributions. However, they still found that the considered settings are very restrictive, maintaining that quadratic discriminators would work only for the very simple type of generators and targets under consideration. Although the article makes important advances towards understanding convergence of WGAN training with nonlinear models, the relevance of the contribution could be greatly enhanced by addressing / discussing the plausibility or implications of the analysis in a practical setting, in the best case scenario addressing a more practical type of neural networks. 
Decision: Reject