Year: 2019

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 optimization problem to global optimality, but are in practice successfully trained using 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 with polynomial time and sample complexity.

heading: 1 INTRODUCTION
text: Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) are a prominent framework for learning generative models of complex, real-world distributions given samples from these distributions. GANs and their variants have been successfully applied to 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., 2017), probabilistic inference (Dumoulin et al., 2016), compressed sensing (Bora et al., 2017) and many more. These advances owe in part to 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 a generated distribution.
Along with the afore-described empirical successes, there have been theoretical studies of the statistical properties of GANs—see e.g. (Zhang et al., 2018; Arora et al., 2017; 2018; Bai et al., 2018; Dumoulin 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 on the stability and convergence properties of gradient 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., 2019; Liang & Stokes, 2019; Mokhtari et al., 2019; Jin et al., 2019; 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. Hence, these works have studied conditions under which GDA converges to a globally optimal solution under a convex-concave objective, or different types of locally optimal solutions under nonconvex-concave or nonconvex-nonconcave 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. (2017) show that for WGANs with a linear generator and quadratic discriminator GDA succeeds in learning a Gaussian using polynomially many samples in the dimension. In the same vein, we are the first to our knowledge to study the global convergence properties of stochastic GDA in the GAN setting, and establishing such guarantees for 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 a large family of functions and a quadratic discriminator, we show that stochastic gradient descent-ascent learns a 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-descent to show it attains a global optimum of the minmax problem, and b) appropriate design of the discriminator to ensure a parametric O( 1√
n ) statistical rate (Zhang
et al., 2018; Bai et al., 2018).
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 at the equilibrium point, GAN training is verified to converge locally for small enough learning rates. A follow-up paper by (Mescheder et al., 2018) shows the necessity of these conditions by identifying a prototypical counterexample that is not 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 a step further, considering WGANs whose generators are one-layer neural networks with a 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 nonconvex-nonconcave min-max optimization problems. 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 convexconcave 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 et 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 convex-concave settings, there is experimental evidence supporting that it improves GAN training (Daskalakis et al., 2017; Gidel et 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., 2016). Some corresponding cures have been proposed. For instance,Zhang et 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 an algorithm to learn the distribution of a 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 learn in polynomial time and sample complexity. Their work instead relies on a specifically tailored algorithm for learning truncated normal distributions Daskalakis et al. (2018).

heading: 2 PRELIMINARIES
text: We consider GAN formulations for learning a generatorGA : Rk → Rd of the form z 7→ x = φ(Az), where A is a d × k parameter matrix and φ some activation function. We consider discriminators Dv : Rd → R or 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 z are sampled from the normal N (0, Ik×k), where Ik×k denotes the identity matrix of size k. The real/target distribution outputs samples x ∼ D = GA∗(N (0, Ik0×k0)), for some ground truth parameters A∗, where A∗ is d× k0, and we take k ≥ k0 for enough expressivity, taking k = d when k0 is unknown. The Wasserstain GAN under our choice of generator and discriminator is naturally formulated as:
min A∈Rd×k max v∈Rd
{ f(A,v) ≡ Ex∼DDv(x)− Ez∼N (0,Ik×k)Dv(GA(z)) } .1
1We will replace v by V ∈ Rd×d when necessary.
We use ai to denote the i-th row vector of A. We sometimes omit the 2 subscript, using ‖x‖ to denote the 2-norm of vector x, and ‖X‖ to denote the spectral norm of matrix X . Sn ⊂ Rn×n represents all the symmetric matrices of dimension n× n. We use Df(X0)[B] to denote the directional derivative of function f at point X0 with direction B: Df(X0)[B] = limt→0 f(X0+tB)−f(X0) t .

heading: 3 WARM-UP: LEARNING THE MARGINAL DISTRIBUTIONS
text: As a warm-up, we ask whether a 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 φ(x) where x ∼ N (0, ‖ai‖2), and is thus solely determined by ‖ai‖2. With a linear discriminator Dv(x) = v>x, our minimax game becomes:
min A∈Rd×k max v∈Rd
{ f1(A,v) ≡ Ex∼D [ v>x ] − Ez∼N (0,Ik×k) [ v>φ(Az) ]} . (1)
Notice that when the activation φ is an odd function, such as the tanh activation, the symmetric property of the Gaussian distribution ensures that Ex∼D[v>x] = 0, hence the linear discriminator in f1 reveals no information about A∗. Therefore specifically for odd activations (or odd plus a constant activations), we instead use an adjusted rectified linear discriminator Dv(x) ≡ v>R(x−C) to enforce some bias, where C = 12 (φ(x) + φ(−x)) for all x, and R denotes the ReLU activation. Formally, we slightly modify our loss function as:
f̄1(A,v) ≡ Ex∼D [ v>R(x− C) ] − Ez∼N (0,Ik×k) [ v>R(φ(Az)− 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 φ satisfies either one of the following: 1. φ is an odd function plus constant, and φ is monotone increasing; 2. The even component of φ, i.e. 12 (φ(x)+φ(−x)), is positive and monotone increasing on x ∈ [0,∞). Remark 1. All common activation functions like (Leaky) ReLU, tanh or sigmoid function satisfy Assumption 1. Lemma 1. Suppose A∗ 6= 0. Consider f1 with activation that satisfies Assumption 1.2 and f̄1 with activation that satisfies Assumption 1.1. The stationary points of such f1 and f̄1 yield parameters A satisfying ‖ai‖ = ‖a∗i ‖,∀i ∈ [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 setting as Lemma 1, alternating gradient descent-ascent with proper learning rates on
min A max v {f1(A,v)− ‖v‖2/2} or respectively min A max v {f̄1(A,v)− ‖v‖2/2}
recovers A such that ‖ai‖ = ‖a∗i ‖,∀i ∈ [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 et al., 2019) of the original problem are global min-max points and recover the correct norm of a∗i ,∀i. Notice for the source data distribution x = (x1, x2, · · ·xd) ∼ D with activation φ, the marginal distribution of each xi follows φ(N (0, ‖a∗i ‖2)) and is determined by ‖a∗i ‖. Therefore we have learned the marginal distribution for each entry i. It remains to learn the joint distribution.

heading: 4 LEARNING THE JOINT DISTRIBUTION
text: In the previous section, we utilize a (rectified) linear discriminator, such that each coordinate vi interacts with the i-th random variable. With the (rectified) linear discriminator, WGAN learns the correct ‖ai‖, for all i. However, since there’s no interaction between different coordinates of the random vector, we do not expect to learn the joint distribution with a linear discriminator.
To proceed, a natural idea is to use a quadratic discriminator DV (x) := x>V x = 〈xx>, V 〉 to enforce component interactions. Similar to the previous section, we study the regularized version:
min A∈Rd×k max V ∈Rd×d
{f2(A, V )− 1
2 ‖V ‖2F }, (3)
where f2(A, V ) = Ex∼DDV (x)− Ez∼N (0,Ik×k)DV (φ(Az)) = 〈 Ex∼D [ xx> ] − Ez∼N (0,Ik×k) [ φ(Az)φ(Az)> ] , V 〉 .
By adding a regularizer on V and explicitly maximizing over V :
g(A) ≡ max V
{ f2(A, V )− 1
2 ‖V ‖2F } = 1
2 ∥∥Ex∼D [xx>]− Ez∼N (0,Ik×k) [φ(Az)φ(Az)>]∥∥2F . 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 .

heading: 4.1 GLOBAL CONVERGENCE FOR OPTIMIZING THE GENERATING PARAMETERS
text: We first assume that both A and A∗ have unit row vectors, and then extend to general case since we already know how to learn the row norms from Section 3. To explicitly compute g(A), we rely on the property of Hermite polynomials. Since normalized Hermite polynomials {hi}∞i=0 forms an orthonomal basis in the functional space, we rewrite the activation function as φ(x) = ∑∞ i=0 σihi, where σi is the i-th Hermite coefficient. We use the following claim:
Claim 1 ((Ge et al., 2017) Claim 4.2). Let φ be a function from R to R such that φ ∈ L2(R, e−x2/2), and let its Hermite expansion be φ = ∑∞ i=1 σihi. Then, for any unit vectors u,v ∈ Rd, we have that
Ex∼N (0,Id×d) [ φ(u>x)φ(v>x) ] = ∞∑ i=0 σ2i (u >v)i.
Therefore we could compute the value of f2 explicitly using the Hermite polynomial expansion:
f2(A, V ) = 〈 ∞∑ i=0 σ2i ( (A∗(A∗)>)◦i − (AA>)◦i ) , V 〉 .
Here X◦i is the Hadamard power operation where (X◦i)jk = (Xjk)i. Therefore we have:
g(A) = 1
2 ∥∥∥∥∥ ∞∑ i=0 σ2i ( (A∗(A∗)>)◦i − (AA>)◦i )∥∥∥∥∥ 2
F
We reparametrize with Z = AA> and define g̃(Z) = g(A) with individual component functions g̃jk(z) ≡ 12 ( ∑∞ i=0 σ 2 i ((z ∗ jk)
i − zi))2. Accordingly z∗jk = 〈a∗j ,a∗k〉 is the (j, k)-th component of the ground truth covariance matrix A∗(A∗)>. Assumption 2. The activation function φ is an odd function plus constant. In other words, its Hermite expansion φ = ∑∞ i=0 σihi satisfies σi = 0 for even i ≥ 2. Additionally we assume σ1 6= 0. Remark 2. Common activations like tanh and sigmoid satisfy Assumption 2. Lemma 2. For activations including leaky ReLU and functions satisfying Assumption 2, g̃(Z) has a unique stationary point where Z = A∗(A∗)>.
Notice g̃(Z) = ∑ jk g̃jk(zjk) is separable across zjk, where each g̃jk is a polynomial scalar function. Lemma 2 comes from the fact that the only zero point for g̃′jk is zjk = z ∗ jk, 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∗i ‖ = 1,∀i:
minA g(A) = 12 ∥∥∥∥∥ ∞∑ i=0 σ2i ( (A∗(A∗)>)◦i − (AA>)◦i )∥∥∥∥∥ 2
F  s.t. a>i ai = 1,∀i.
Existing work Journée et al. (2008) connects g̃(Z) to the optimization over factorized version for g(A) (g(A) ≡ g̃(AA>)). Specifically, when k = d, all second-order stationary points for g(A) are first-order stationary points for g̃(Z). Though g̃ is not convex, we are able to show that its first-order stationary points are global optima when the generator is sufficiently expressive, i.e., k ≥ k0. In reality we won’t know the latent dimension k0, 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 1 are its global minimum. Therefore alternating projected gradient descent-ascent on Eqn. (3) converges to A : AA> = A∗(A∗)>.
The extension for non-unit vectors is straightforward, and we defer the analysis to the Appendix.

heading: 5 FINITE SAMPLE ANALYSIS
text: Algorithm 1 Online stochastic gradient descent ascent on WGAN 1: Input: n training samples: x1,x2, · · ·xn, where each xi ∼ φ(A∗z), z ∼ N (0, Ik×k), learning
rate for generating parameters η, number of iterations T . 2: Random initialize generating matrix A(0). 3: for t = 1, 2, · · · , T do 4: Generatem latent variables z(t)1 , z (t) 2 , · · · , z (t) m ∼ N (0, Ik×k) for the generator. The empirical
function becomes
f̃ (t)m,n(A, V ) =
〈 1
m m∑ i=1 φ(Az (t) i )φ(Az (t) i ) > − 1 n n∑ i=1 xix > i , V
〉 − 1
2 ‖V ‖2
5: Gradient ascent on V with optimal step-size ηV = 1:
V (t) ← V (t) − ηV∇V f̃ (t)m,n(A(t−1), V (t−1)).
6: Sample noise e uniformly from unit sphere 7: Projected Gradient Descent on A, with constraints C = {A|(AA>)ii = (A∗A∗>)ii} :
A(t) ← ProjC(A(t−1) − η(∇Af̃ (t)m,n(A(t−1), V (t)) + e)).
8: end for 9: Output: A(T )(A(T ))>
In this section, we consider analyzing Algorithm 1, i.e., gradient descent ascent on the following:
f̃ (t)m,n(A, V ) =
〈 1
m m∑ i=1 φ(Az (t) i )φ(Az (t) i ) > − 1 n n∑ i=1 xix > i , V
〉 − 1
2 ‖V ‖2. (4)
Notice in each iteration, gradient ascent with step-size 1 finds the optimal solution for V . By Danskin’s theorem (Danskin, 2012), our min-max optimization is essentially gradient descent over g̃ (t) m,n(A) ≡ maxV f̃ (t)m,n(A, V ) = 12‖ 1 m ∑m i=1 φ(Az (t) i )φ(Az (t) i ) > − 1n ∑n i=1 xix > i ‖2F with a batch of samples {z(t)i }, i.e., stochastic gradient descent for fn(A) ≡ Ezi∼N (0,Ik×k),∀i∈[m][g̃m,n(A)].
Therefore to bound the difference between fn(A) and the population risk g(A), we analyze the sample complexity required on the observation side (xi ∼ D, i ∈ [n]) and the mini-batch size required on the learning part (φ(Azj), zj ∼ N (0, Ik×k), j ∈ [m]). We will show that with large enough n,m, the algorithm specified in Algorithm 1 that optimizes over the empirical risk will yield the ground truth covariance matrix with high probability.
Our proof sketch is roughly as follows:
1. With high probability, projected stochastic gradient descent finds a second order stationary point Â of fn(·) as shown in Theorem 31 of (Ge et al., 2015).
2. For sufficiently large m, our empirical objective, though a biased estimator of the population risk g(·), achieves good -approximation to the population risk on both the gradient and Hessian (Lemmas 4&5). Therefore Â is also an O( )-approximate second order stationary point (SOSP) for the population risk g(A).
3. We show that any -SOSP Â for g(A) yields anO( )-first order stationary point (FOSP) Ẑ ≡ ÂÂ> for the semi-definite programming on g̃(Z) (Lemma 6).
4. We show that any O( )-FOSP of function g̃(Z) induces at most O( ) absolute error compared to the ground truth covariance matrix Z∗ = A∗(A∗)> (Lemma 7).

heading: 5.1 OBSERVATION SAMPLE COMPLEXITY
text: For simplicity, we assume the activation and its gradient satisfy Lipschitz continuous, and let the Lipschitz constants be 1 w.l.o.g.: Assumption 3. Assume the activation is 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:
g(A) ≡ 1 2 ∥∥Ex∼D [xx>]− Ez∼N (0,Ik×k) [φ(Az)φ(Az)>]∥∥2F , and gn(A) ≡ 1
2 ∥∥∥∥∥ 1n n∑ i=1 xix > i − Ez∼N (0,Ik×k) [ φ(Az)φ(Az)> ]∥∥∥∥∥ 2
F
.
Claim 2. ∇g(A)−∇gn(A) = 2Ez [ diag(φ′(Az))(X −Xn)φ(Az)z> ] ,
where X = Ex∼D[xx>], and Xn = 1n ∑n i=1 xix > i . The directional derivative with arbitrary direction B is:
D∇g(A)[B]−D∇gn(A)[B] = 2Ez [ diag(φ′(Az))(Xn −X)φ′(Az) ◦ (Bz)z> ] + 2Ez [ diag(φ′′(Az) ◦ (Bz))(Xn −X)φ(Az)z>
] Lemma 3. Suppose the activation satisfies Assumption 3. Pr[‖X − Xn‖ ≤ ‖X‖] ≥ 1 − δ, for n ≥ Θ̃(d/ 2 log2(1/δ))2. Lemma 4. Suppose the activation satisfies Assumption 2&3. With samples n ≥ Θ̃(d/ 2 log2(1/δ)), ‖∇g(A) − ∇gn(A)‖2 ≤ O( d‖A‖2) with probability 1 − δ. Meanwhile, ‖D∇g(A)[B] − D∇gn(A)[B]‖2 ≤ O( d3/2‖A‖2‖B‖2) with probability 1− δ.

heading: 5.2 BOUNDING MINI-BATCH SIZE
text: Normally for empirical risk for supervised learning, the mini-batch size can be arbitrarily small since the estimator of the gradient is unbiased. However in the WGAN setting, notice for each iteration, we randomly sample a batch of random variables {zi}i∈[m], and obtain a gradient of
g̃m,n(A) ≡ 12 ∥∥∥ 1n∑ni=1 xix>i − 1m∑mj=1 φ(Azj)φ(Azj)>∥∥∥2
F , in Algorithm 1. 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 gn(A) = 12 ∥∥ 1 n ∑n i=1 xix > i − Ez [ φ(Az)φ(Az)> ]∥∥2 F .
In other words, we conduct stochastic gradient descent over the function f(A) ≡ Ez g̃m,n(A). Therefore we just need to analyze the gradient error between this f(A) and gn(A) (i.e. g̃m,n is almost an unbiased estimator of gn). Finally with the concentration bound derived in last section, we get the error bound between f(A) and g(A). Lemma 5. The empirical risk g̃m,n is almost an unbiased estimator of gn. Specifically, the expected function f(A) = Ezi∼N (0,Ik×k),i∈[m][g̃m,n] satisfies:
‖∇f(A)−∇gn(A)‖ ≤ O( 1
m ‖A‖3d2).
2Θ̃ hides log factors of d for simplicity.
For arbitrary direction matrix B,
‖D∇f(A)[B]−D∇gn(A)[B]‖ ≤ O( 1
m ‖B‖‖A‖3d5/2).
In summary, we conduct concentration bound over the observation samples and mini-batch sizes, and show the gradient of f(A) that Algorithm 1 is optimizing over has close gradient and Hessian with the population risk g(A). Therefore a second-order stationary point (SOSP) for f(A) (that our algorithm is 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) ≡ g(A),∀Z = AA>.

heading: 5.3 RELATION ON APPROXIMATE OPTIMALITY
text: In this section, we establish the relationship between g̃ and g. We present the general form of our target Problem 1:
minA∈Rd×k g(A) ≡ g̃(AA>) (5) s.t. Tr(A>XiA) = yi, Xi ∈ S, yi ∈ R, i = 1, · · · , n.
Similar to the previous section, the stationary property might not be obvious on the original problem. Instead, we could look at the re-parametrized version as:
minZ∈S g̃(Z) (6) s.t. Tr(XiZ) = yi, Xi ∈ S, yi ∈ R, i = 1, · · · , n,
Z 0, Definition 1. A matrix A ∈ Rd×k is called an -approximate second-order stationary point ( -SOSP) of Eqn. (5) if there exists a vector λ such that: Tr(A >XiA) = yi, i ∈ [n] ‖(∇Z g̃(AA>)− ∑n i=1 λiXi)ãj‖ ≤ ‖ãj‖, {ãj}j span the column space of A Tr(B>D∇AL(A, λ)[B]) ≥ − ‖B‖2, ∀B s.t. Tr(B>XiA) = 0 Here L(A, λ) is the Lagrangian form g̃(AA>)− ∑n i=1 λi(Tr(A >XiA)− yi).
Specifically, when = 0 the above definition is exactly the second-order KKT condition for optimizing (5). Next we present the approximate first-order KKT condition for (6): Definition 2. A symmetric matrix Z ∈ Sn is an -approximate first order stationary point of function (6) ( -FOSP) if and only if there exist a vector σ ∈ Rm and a symmetric matrix S ∈ S such that the following holds: Tr(XiZ) = yi, i ∈ [n] Z 0, S − I, ‖Sãj‖ ≤ ‖ãj‖, {ãj}j span the column space of Z S = ∇Z g̃(Z)− ∑n i=1 σiXi. Lemma 6. Let latent dimension k = d. For an -SOSP of function (5) with A and λ, it infers an -FOSP of function (6) with Z, σ and S that satisfies: Z = AA>, σ = λ and S = ∇Z g̃(AA>) −∑ i λiXi.
Now it remains to show an -FOSP of g̃(Z) indeed yields a good approximation for the ground truth parameter matrix. Lemma 7. If Z is an -FOSP of function (6), then ‖Z −Z∗‖F ≤ O( ). Here Z∗ = A∗(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 size3: Theorem 3. For arbitrary δ < 1, , given small enough learning rate η < 1/poly(d, 1/ , log(1/δ)), let sample size n ≥ Θ̃(d5/ 2 log2(1/δ)), batch size m ≥ O(d5/ ), for large enough T=poly(1/η, 1/ , d, log(1/δ)), the output of Algorithm 1 satisfies ‖A(T )(A(T ))> − Z∗‖F ≤ O( ) with probability 1− δ, under Assumptions 2 & 3 and k = d.
3The exact error bound comes from the fact that when diagonal terms of AA> are fixed, ‖A‖2 = O( √ d).

heading: 6 SIMULATIONS
text: 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 on Algorithm 1 that targets to recover the parameter matrix. We conduct a thorough empirical studies on three joint factors that might affect the performance: the number of observed samples m (we set n = m as in general GAN training algorithms), the different choices of activation function φ, and the output dimension d. In Figure 1 we plot the relative error for parameter estimation decrease over the increasing sample complexity. We fix the hidden dimension k = 2, and vary the output dimension over {3, 5, 7} and sample complexity over {500, 1000, 2000, 5000, 10000}. Reported values are averaged from 20 runs and we show the standard deviation with the corresponding colored shadow. Clearly the recovery error decreases with higher sample complexity and smaller output dimension.
To visually demonstrate the learning process, we also include a simple comparison for different φ: i.e. leaky ReLU and tanh activations, when k = 1 and d = 2. We set the ground truth covariance matrix to be [1, 1; 1, 1], and therefore a valid result should be [1, 1] or [−1,−1]. From Figure 2 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.

heading: 7 CONCLUSION
text: We analyze the convergence of stochastic gradient descent ascent for Wasserstein GAN on learning a 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 Θ̃(d5/ 2) i.i.d samples.

heading: A OMITTED PROOF FOR LEARNING THE DISTRIBUTION

heading: A.1 STATIONARY POINT FOR MATCHING FIRST MOMENT
text: Proof of Lemma 1. To start with, we consider odd-plus-constant monotone increasing activations. Notice that by proposing a rectified linear discriminator, we have essentially modified the activation function as φ̃ := R(φ− C), where C = 12 (φ(x) + φ(−x)) is the constant bias term of φ. Observe that we can rewrite the objective f̄1 for this case as follows:
f1(A,v) = Ez∼N (0,Ik0×k0 )v >φ̃(A∗z)− Ez∼N (0,Ik×k)v >φ̃(Az).
Moreover, notice that φ̃ is positive and increasing on its support which is [0,+∞). Now let us consider the other case in our statement where φ has a positive and monotone increasing even component in [0,+∞). In this case, let us take:
φ̃(x) = { φ(x) + φ(−x), x ≥ 0 0, o.w.
Because of the symmetry of the Gaussian distribution, we can rewrite the objective function for this case as follows:
f1(A,v) = Ez∼N (0,Ik0×k0 )v >φ̃(A∗z)− Ez∼N (0,Ik×k)v >φ̃(Az).
Moreover, notice that φ̃ is positive and increasing on its support which is [0,+∞).
To conclude, in both cases, the optimization objective can be written as follows, where φ̃ satisfies Assumption 1.2 and is only non-zero on [0,+∞).
f1(A,v) = Ez∼N (0,Ik0×k0 )v >φ̃(A∗z)− Ez∼N (0,Ik×k)v >φ̃(Az).
The stationary points of the above objective satisfy:{ ∇vf1(A,v) = Ez∼N (0,Ik0×k0 )φ̃(A
∗z)− Ez∼N (0,Ik×k)φ̃(Az) = 0, ∇ajf1(A,v) = −Ez∼N (0,Ik×k)vj φ̃′(a>j z)z = 0.
We focus on the gradient over v. To achieve ∇vf1(A,v) = 0, the stationary point satisfies: ∀j,Ez∼N (0,Ik0×k0 )φ̃((a ∗ j ) >z) = Ez∼N (0,Ik×k)φ̃(a > j z), i.e.
∀j,Ex∼N (0,‖a∗j ‖2)φ̃(x) = Ex′∼N (0,‖aj‖2)φ̃(x ′). (7)
To recap, for activations φ that follow Assumption 1, in both cases we have written the necessary condition on stationary point to be Eqn. (7), where φ̃ is defined differently for odd or non-odd activations, but in both cases it is positive and monotone increasing on its support [0,∞). We then argue the only solution for Eqn. (7) satisfies ‖aj‖ = ‖a∗j‖,∀j. This follows directly from the following claim:
Claim 3. The function h(α) := Ex∼N (0,α2)f(x), α > 0 is a monotone increasing function if f is positive and monotone increasing on its support [0,∞).
We could see from Claim 3 that the LHS and RHS of Eqn. (7) is simply h(‖aj‖) and h(‖a∗j‖) for each j. Now that h is an monotone increasing function, the unique solution for h(‖aj‖) = h(‖a∗j‖) is to match the norm: ‖aj‖ = ‖a∗j‖,∀j.
Proof of Claim 3.
h(α) = Ex∼N (0,α2)f(x)
=
∫ ∞ 0 f(x)e− x2 2α2 dx
y:=x/α = ∫ ∞ 0 αf(αy)e− y2 2 dy
= Ey∼N (0,1)αf(αy).
Notice h′(α) = Ex∼N (0,1)[αxf ′(αx) + f(αx)]. Since f , f ′, and α > 0, and we only care about the support of f where x is also positive, therefore h′ is always positive and h is monotone increasing.
To sum up, at stationary point where ∇f1(A,v) = 0, we have
∀i, ‖a∗i ‖ = ‖ai‖.

heading: A.2 PROOF OF THEOREM 1
text: Proof of Theorem 1. We will take optimal gradient ascent steps with learning rate 1 on the discriminator side v, hence the function we will actually be optimizing over becomes (using the notation for φ̃ from section A.1):
h(A) = max v
f1(A,v) = 1
2 ∥∥∥Ez∼N (0,Ik0×k0 )φ̃(A∗z)− Ez∼N (0,Ik×k)φ̃(Az)∥∥∥2 . We just want to verify that there’s no spurious local minimum for h(A). Notice there’s no interaction between each row vector of A. Therefore we instead look at each hi := 1 2 ( Ez∼N (0,Ik0×k0 )φ̃((a ∗ i ) >z)− Ez∼N (0,Ik×k)φ̃(a>i z) )2 for each i. Now ∇hi(ai) =
− ( Ez∼N (0,Ik0×k0 )φ̃((a ∗ i ) >z)− Ez∼N (0,Ik×k)φ̃(a>i z) ) (Ez∼N (0,Ik×k)zφ̃′(a>i z)). Due to the symmetry of the Gaussian, we take ai = ae1, where a = ‖ai‖. It is easy to see that checking whether Ez∼N (0,Ik×k)zφ̃′(a>i z) = 0 is equivalent to checking whether Ez1∼N (0,1)z1φ̃′(az1) = 0.
Recall that φ̃ is supported on [0,+∞) and it is monotonically increasing on its support. Hence, Ez1∼N (0,1)z1φ̃′(az1) 6= 0 unless a = 0. Hence, suppose ‖ai‖ 6= 0,∀i. Then ∇Ah(A) = 0 iff h(A) = 0, i.e. Ez∼N (0,Ik0×k0 )φ̃(A ∗z) = Ez∼N (0,Ik×k)φ̃(Az).
Therefore all stationary points of h(A) are global minima where Ez∼N (0,Ik0×k0 )φ̃(A ∗z) = Ez∼N (0,Ik×k)φ̃(Az) and according to Lemma 1, this only happens when ‖ai‖ = ‖a∗i ‖,∀i ∈ [d].

heading: A.3 STATIONARY POINTS FOR WGAN WITH QUADRATIC DISCRIMINATOR
text: Proof of Lemma 2. To study the stationary point for g̃(Z) = ∑ jk g̃jk(zjk), we look at individual
g̃jk(z) ≡ 12 ( ∑∞ i=0 σ 2 i ((z ∗ jk)
i − zi))2. Notice for odd-plus-constant activations, σi is zero for even i > 0. Recall our assumption in Lemma 2 also requires that σ1 6= 0. Since the analysis is invariance to the position of the matrix Z, we simplify the notation here and essentially want to study the stationary point for f(a) = 12 ( ∑ i odd σ 2 i (a
i− bi))2 for some constant b and σi, where σ1 6= 04.
f ′(a) = (∑ i odd σ2i (a i − bi) )(∑ i odd iσ2i a i−1 )
= (a− b) σ21 + ∑ i≥3 odd σ2i ai − bi a− b σ21 + ∑ i≥3 odd iσ2i a i−1  = (a− b)(I)(II).
Notice now f ′(a) = 0⇔ a = b. This is because the polynomial f ′(a) is factorized to a− b and two factors I and II that are always positive. Notice here we use a
i−bi a−b to denote ∑i j=0 a
jbi−j , which is always nonnegative. This is simply because ai − bi always shares the same sign as a− b when i is odd. Therefore I=σ21 + ∑ i≥3 odd σ 2 i ai−bi a−b > 0,∀a.
4The zero component has been cancelled out.
Meanwhile, since ai−1 is always nonnegative for each odd i, we have II= σ21 + ∑ i≥3 odd iσ 2 i a i−1 is also always positive for any a.
Next, for activation like ReLU, loss g̃jk(z) = 12 (h(z)−h(z ∗ jk)) 2, where h(x) = 1π ( √
1− x2 + (π− cos−1(x))x) (Daniely et al., 2016). Therefore h′(−1) = 0 for any z∗jk. This fact prevents us from getting the same conclusion for ReLU.
However, for leaky ReLU with coefficient of leakage α ∈ (0, 1), φ(x) = max{x, αx} = (1 − α)ReLU(x) + αx.
We have
Ez∼N (0,Ik×k [ φ(a>i z)φ(a > j z) ] =(1− α)2EzReLU(a>i z)ReLU(a>j z) + (1− α)αEzReLU(a>i z)a>j z
+ (1− α)αEza>i zReLU(a>j z) + α2Eza>i za>j z =(1− α)2h(a>i aj) + αa>i aj
Therefore for leaky ReLU g̃jk(z) = 12 ((1 − α) 2(h(z) − h(zjk∗)) + α(z − z∗jk))2, and g̃′jk(z) = ((1−α)2(h(z)−h(zjk∗))+α(z−z∗jk))((1−α)2h′(z)+α).Now with α > 0, (1−α)2h′(z)+α ≥ α for all z and g̃jk(z) = 0⇔ z = z∗jk.
To sum up, for odd activations and leaky ReLU, since each g̃jk(z) only has stationary point of z = z∗jk, the stationary point Z of g̃(Z) = ∑ jk g̃jk also satisfy Z = Z ∗ = A∗(A∗)>.
Proof of Theorem 2. Instead of directly looking at the second-order stationary point of Problem 1, we look at the following problem on its reparametrized version:
Problem 2.
minZ g̃(Z) = 12 ∥∥∥∥∥ ∞∑ i=0 σ2i ( (Z∗)◦i − Z◦i )∥∥∥∥∥ 2
F  s.t. zii = 1,∀i.
Z 0.

heading: Here Z∗ = A∗(A∗)> and satisfies z∗ii = 1,∀i.
text: Compared to function g in the original problem 1, it satisfies that g̃(AA>) ≡ g(A). A matrix Z satisfies the first-order stationary point for Problem 2 if there exists a vector σ such that:
 zii = 1, Z 0, S 0, SZ = 0, S = ∇Zg(Z)− diag(σ).
Therefore for a stationary point Z, since Z∗ = A∗(A∗)> 0, and S 0, we have 〈S,Z∗ − Z〉 = 〈S,Z∗〉 ≥ 0. Meanwhile,
〈Z∗ − Z, S〉 =〈Z∗ − Z,∇Zf(Z)− diag(σ)〉 =〈Z∗ − Z,∇Zf(Z)〉 (diag(Z∗ − Z) = 0)
= ∑ i,j (z∗ij − zij)g′ij(zij)
= ∑ i,j (zij − z∗ij)P (zij)(z∗ij − zij)
(Refer to proof of Lemma 2 for the value of g′) =− ∑ ij (zij − z∗ij)2P (zij)
≤0 (P is always positive)
Therefore 〈S,Z∗ − Z〉 = 0, and this only happens when Z = Z∗. Finally, from Journée et al. (2008) we know that any first-order stationary point for Problem 2 is a second-order stationary point for our original problem 1 5. Therefore we conclude that all second-order stationary point for Problem 1 are global minimum A: AA> = A∗(A∗)>.

heading: A.4 LANDSCAPE ANALYSIS FOR NON-UNIT GENERATING VECTORS
text: In the previous argument, we simply assume that the norm of each generating vectors ai to be 1. This practice simplifies the computation but is not practical. Since we are able to estimate ‖ai‖ for all i first, we could analyze the landscape of our loss function for general matrix A.
The main tool is to use the multiplication theorem of Hermite functions:
hαn(x) := hn(αx) = bn2 c∑ i=0 αn−2i(α2 − 1)i ( n 2i ) (2i)! i! 2−ihn−2i(x).
For the ease of notation, we denote the coefficient as ηn,iα := α n−2i(α2− 1)i ( n 2i ) (2i)! i! 2
−i. We extend the calculations for Hermite inner product for non-standard distributions.
Lemma 8. Let (x, y) be normal variables that follow joint distributionN (0, [[α2, αβρ]; [αβρ, β2]]). Then,
E[hm(x)hn(y)] =
{ ∑b l2 c i=0 η l,i α η l,i β ρ
l−2i if m ≡ n (mod 2) 0 o.w.
(8)
Here l = min{m,n}.
5Throughout the analysis for low rank optimization in Journée et al. (2008), 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-order stationary points of g(A) and g̃(Z). For more cautious readers, we also show a relaxed version in the next section, where the equivalence of SOSP of g and FOSP of g̃ is a special case of it.
Proof. Denote the normalized variables x̂ = x/α, ŷ = y/β. Let l = min{m,n}. E[hm(x)hn(y)]
=E[hαm(x̂)hβn(ŷ)]
= bm2 c∑ i=0 bn2 c∑ j=0 ηm,iα η n,j β E[hm−2i(x̂)hn−2j(ŷ)]
= bm2 c∑ i=0 bn2 c∑ j=0 ηm,iα η n,j β δ(m−2i),(n−2j)ρ n−2j (Lemma ??)
=
{ ∑b l2 c i=0 η l,i α η l,i β ρ
l−2i if m ≡ n (mod 2) 0 o.w. .
Now the population risk becomes
g(A) = 1
2 ∥∥Ex∼D [xx>]− Ez∼N (0,Ik×k) [φ(Az)φ(Az)>]∥∥2 = 1
2 ∑ i,j∈[d] ( Ez∼N (0,Ik0×k0 )φ((a ∗ i ) >z)φ((a∗j ) >z)− Ez∼N (0,Ik×k)φ(a > i z)φ(a > j z) )2 ≡1
2 ∑ i,j g̃ij(zij).
To simplify the notation, for a specific i, j pair, we write x̂ = a>i z/α, α = ‖ai‖ and ŷ = a>j z/β, where β = ‖aj‖. Namely we have (x̂, ŷ) ∼ N (0, [[1, ρ]; [ρ, 1]]), where ρ = cos〈ai,aj〉. Again, recall φ(αx̂) = ∑ k odd σihi(αx̂) = ∑ k odd σih α i (x̂).
Ez∼N (0,Ik×k)[φ(αx̂)φ(βŷ)]
=E [∑ m odd σmh α m(x̂) ∑ n odd σnh β n(ŷ) ] = ∑
m,n odd
σmσnES [hαm(x̂)hβn(ŷ)]
= ∑ m odd σm ∑ n≤m odd σn bn2 c∑ k=0 ηn,kα η n,k β ρ n−2k
Therefore we could write out explicitly the coefficient for each term ρk, k odd, as: ck =∑ n≥k odd σnη n,n−k2 α η n,n−k2 β ( ∑ m≥n σm). We have g̃ij(zij) = ( ∑ k odd ckz k ij − ∑ k odd ck(z ∗ ij) k)2.
Now suppose σi to have the same sign, and ‖αi‖ ≥ 1,∀ or ‖αi‖ ≤ 1,∀i, each coefficient ci ≥ 0. Therefore still the only stationary point for g(Z) is Z∗.

heading: B OMITTED PROOFS FOR SAMPLE COMPLEXITY

heading: B.1 OMITTED PROOFS FOR RELATION ON APPROXIMATE STATIONARY POINTS
text: Proof of Lemma 6. We first review what we want to prove. For a matrixA that satisfies -approximate SOSP for Eqn. (5), we define SA = ∇Z g̃(AA>)− ∑n i=1 λiXi. The conditions ensure that A, λ, SA satisfy:  Tr(A >XiA) = yi,
‖SAãi‖2 ≤ ‖ãi‖2, {ãj}j span the column space of A Tr(B>DA∇AL(A, λ)[B]) ≥ − ‖B‖2F , ∀B s.t. Tr(B>XiA) = 0.
(9)
We just want to show Z := AA>, σ := λ, and S := SA satisfies the conditions for -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 SA − I . By noting that∇AL(A, λ) = 2SAA, one has:
1 2 Tr(B>DA∇AL(A, λ)[B])
= Tr(B>SAB) + Tr(B >DA∇Z g̃(AA>)[B]A)− n∑ i=1 DAλi[B] Tr(B >XiA)
(from Lemma 5 of Journée et al. (2008))
= Tr(B>SAB) + Tr(AB >DA∇Z g̃(AA>)[B]) (10)
(From Eqn. (9) we have Tr(B>XiA) = 0)
Notice that A ∈ Rd×k and we have chosen k = d for simplicity. We first argue when A is rankdeficient, i.e. rank(A) < k. There exists some vector v ∈ Rk such that Av = 0. Now for any vector b ∈ Rd, let B = bv>. Therefore AB> = Avb> = 0. From (10) we further have:
1 2 Tr(B>DA∇AL(A, λ)[B])
= Tr(B>SAB) + Tr(AB >DA∇Z g̃(AA>)[B])
= Tr(vb>SAbv >) = ‖v‖2b>SAb
≥− /2‖B‖2F (from (9)) =− /2‖v‖2‖b>‖2
Therefore from the last three rows we have b>SAb ≥ − /2‖b‖2 for any b, i.e. SA − /2Id×d. On the other hand, when A is full rank, the column space of A is the entire Rd vector space, and therefore SA − Id×d directly follows from the second line of the -SOSP definition.

heading: B.2 DETAILED CALCULATIONS
text: Recall the population risk
g(A) ≡ 1 2 ∥∥Ex∼D [xx>]− Ez∼N (0,Ik×k) [φ(Az)φ(Az)>]∥∥2F . Write the empirical risk on observations as:
gn(A) ≡ 1
2 ∥∥∥∥∥ 1n n∑ i=1 xix > i − Ez∼N (0,Ik×k) [ φ(Az)φ(Az)> ]∥∥∥∥∥ 2
F
.
Claim 4. ∇g(A)−∇gn(A) = 2Ez [ diag(φ′(Az))(X −Xn)φ(Az)z> ] ,
where X = Ex∼D[xx>], and Xn = 1n ∑n i=1 xix > i .
Proof.
∇g(A)−∇gn(A) = ∇(g(A)− gn(A))
= 1 2 ∇ 〈 X −Xn, X +Xn − 2Ez∼N (0,Ik×k) [ φ(Az)φ(Az)> ]〉 =∇ 〈 Xn −X,Ez∼N (0,Ik×k) [ φ(Az)φ(Az)>
]〉 Now write S(A) = φ(Az)φ(Az)>.
[S(A+ ∆A)− S(A)]ij =φ(a>i z + ∆a > i z)φ(a > j z + ∆a > j z)− φ(a>i z)φ(a>j z) =φ′(a>i z)∆a > i zφ(a > j z) + φ ′(a>j z)∆a > j zφ(a > i z) +O(‖∆A‖2)
Therefore
[S(A+ ∆A)− S(A)]i: =φ′(a>i z)∆a > i zφ(Az) > + (φ′(Az) ◦∆Az)>φ(a>i z) +O(‖∆A‖2)
Therefore
S(A+ ∆A)− S(A) = diag(φ′(Az))∆Azφ(Az)> + φ(Az)z>∆A>diag(φ′(Az)). (11)
And
g(A+ ∆A)− gn(A+ ∆A)− (g(A)− gn(A)) =〈Xn −X,Ez [S(A+ ∆A)− S(A)]〉 =Ez〈Xn −X, diag(φ′(Az))∆Azφ(Az)> + φ(Az)z>∆A>diag(φ′(Az))〉 =2Ez〈diag(φ′(Az))(Xn −X)φ(Az)z>,∆A〉.
Finally we have ∇g(A)−∇gn(A) = 2Ez [ diag(φ′(Az))(Xn −X)φ(Az)z> ] .
Claim 5. For arbitrary matrix B, the directional derivative of ∇g(A)−∇gn(A) with direction B is:
DA∇g(A)[B]−DA∇gn(A)[B] = 2Ez [ diag(φ′(Az))(Xn −X)φ′(Az) ◦ (Bz)z> ] +2Ez [ diag(φ′′(Az) ◦ (Bz))(Xn −X)φ(Az)z>
] Proof.
g(A+ tB) =2Ez [ diag(φ′(Az + tBz))(Xn −X)φ(Az + tBz)z> ] =2Ez [ diag(φ′(Az) + t(Bz) ◦ φ′′(Az))(Xn −X)(φ(Az) + tφ′(Az) ◦ (Bz))z> ] +O(t2)
Therefore
lim t→0 g(A+ tB)− g(A) t
=2Ez [ diag(φ′(Az))(Xn −X)φ′(Az) ◦ (B>z)z> ] + 2Ez [ diag(φ′′(Az) ◦ (Bz))(Xn −X)φ(Az)z> ]

heading: B.3 OMITTED PROOFS FOR OBSERVATION SAMPLE COMPLEXITY
text: Proof of Lemma 3. For each xi = φ(Azi), zi ∼ N (0, Ik×k). Each coordinate |xi,j | = |φ(a>j zi)| ≤ |a>j zi| since φ is 1-Lipschitz. 6. Without loss of generality we assumed ‖aj‖ = 1,∀j, therefore a>j z ∼ N (0, Ik×k). For all i ∈ [n], j ∈ [d] |xi,j | ≤ log(nd/δ) with probability 1− δ. Then by matrix concentration inequality ((Vershynin, 2010) Corollary 5.52), we have with probability 1−δ: (1− )X Xn (1+ )X if n ≥ Ω(d/ 2 log2(nd/δ)). Therefore set n = Θ̃(d/ 2 log2(1/δ)) will suffice.

heading: Proof of Lemma 4.
text: Xij = Ez∼N (0,Ik×k)φ(a > i z)φ(a > j z)
= { 0 i 6= j E[φ2(a>i z)] ≤ 2π i = j
6For simplicity, we analyze as if φ(0) = 0 w.o.l.g. throughout this section, since the bias term is canceled out in the observation side with φ(A∗z) and the learning side with φ(Az).
Therefore ‖X‖2 ≤ 2π . Together with Lemma 3, ‖X −Xn‖ ≤ 2 π w.p 1− δ. Recall ∇g(A)−∇gn(A) = 2Ez [ diag(φ′(Az))(X −Xn)φ(Az)z> ] := 2EzG(z), whereG(z) is defined as diag(φ′(Az))(X−Xn)φ(Az)z>. We have ‖G(z)‖ ≤ ‖A‖‖z‖2‖X−Xn‖. ‖∇g(A)−∇gn(A)‖2 = 2‖Ez[G(z)]‖
≤ 2Ez‖G(z)‖ ≤ 2Ez‖A‖‖z‖2‖X −Xn‖
≤ 2‖A‖ 2 π Ez‖z‖2 = 2‖A‖ d 2 π
For the directional derivative, we make the concentration bound in a similar way. Denote D(z) = diag(φ′(Az))(Xn −X)φ′(Az) ◦ (Bz)z> + diag(φ′′(Az) ◦ (Bz))(Xn −X)φ(Az)z>.
‖D(z)‖ ≤ ‖Xn −X‖2‖B‖‖z‖2(1 + ‖z‖‖A‖). Therefore ‖DA∇g(A)[B]−DA∇gn(A)[B]‖ ≤ O( d3/2‖A‖‖B‖) with probability 1− δ.

heading: B.4 OMITTED PROOFS ON BOUNDING MINI-BATCH SIZE
text: Recall
g̃m,n(A) ≡ 1
2 ∥∥∥∥∥∥ 1n n∑ i=1 xix > i − 1 m m∑ j=1 φ(Azj)φ(Azj) > ∥∥∥∥∥∥ 2
F
.
Write Sj(A) ≡ φ(Azj)φ(Azj)>. Then we have
g̃m,n(A) = 1
2
〈 Xn − 1
n m∑ j=1 Sj(A), Xn − 1 m m∑ j=1 Sj(A)
〉
= 1
2m2 ∑ i,j 〈Si(A), Sj(A)〉 − 1 n m∑ j=1 〈Sj(A), Xn〉+ 1 2 ‖Xn‖2F
On the other hand, our target function is:
gn(A) ≡ 1
2 ∥∥∥∥∥ 1n n∑ i=1 xix > i − Ez∼N (0,Ik×k) [ φ(Az)φ(Az)> ]∥∥∥∥∥ 2
F
= 1
2 ‖ES [S]‖2F − 〈ES [S], Xn〉+
1 2 ‖Xn‖2F
Therefore ES g̃m,n(A)− gn(A) = 12m (ES‖S(A)‖ 2 F − ‖ESS(A)‖2F ). Claim 6. ∇ES g̃m,n(A)−∇gn(A) = 2 m Ez [ diag(φ′(Az))S(A)φ(Az)z> − diag(φ′(Az))ES [S(A)]φ(Az)z> ] .
Proof. 〈∇ES g̃m,n −∇gn,∆A〉
=ES g̃m,n(A+ ∆A) + gn(A+ ∆A)− (ES g̃m,n(A) + gn(A)) +O(‖∆A‖2)
= 1
2m
( ES‖S(A+ ∆A)‖2F − ES‖S(A)‖2F − ‖ESS(A+ ∆A)‖2F + ‖ESS(A)‖2F ) +O(‖∆A‖2)
= 1
m (ES〈S(A), S(A+ ∆A)− S(A)〉 − 〈ES [S(A)], ES [S(A+ ∆A)− S(A)]) +O(‖∆A‖2)
= 1
m
( 〈Ez〈S(A), diag(φ′(Az))∆Azφ(Az)>〉 − 〈ES [S(A)],Ezdiag(φ′(Az))∆Azφ(Az)>〉 ) +O(‖∆A‖2) (from Eqn. (11) and symmetry of S)
=〈 2 m Ez [ diag(φ′(Az))S(A)φ(Az)z> − diag(φ′(Az))ES [S(A)]φ(Az)z> ] ,∆A〉+O(‖∆A‖2)
Similarly to the derivation in the previous subsection, we again derive the bias in the directional derivative: Claim 7. For arbitrary matrix direction B,
DA∇ES g̃m,n(A)[B]−DA∇gn(A)[B]
= 2 m Ez [ diag(φ′′(Az) ◦ (Bz))(S(A)− ESS(A))φ(Az)z>
+ diag(φ′(Az)) ( (φ′(Az) ◦ (Bz))φ(Az)> − Ez[(φ′(Az) ◦ (Bz))φ(Az)>] ) φ(Az)z>
+ diag(φ′(Az)) ( φ(Az)(φ′(Az) ◦ (Bz))> − Ez[φ(Az)(φ′(Az) ◦ (Bz))>] ) φ(Az)z>
+ diag(φ′(Az))(S(A)− ESS(A))(φ′(Az) ◦ (Bz))z> ]

heading: B.5 OMITTED PROOF OF THE MAIN THEOREM
text: Proof of Lemma 7. On one hand, suppose Z is an -FOSP property of g̃ in (6) along with the matrix S and vector σ, we have:
〈∇g̃(Z), Z − Z∗〉 =〈S,Z − Z∗〉
(since Z − Z∗ has 0 diagonal entries) ≤‖PT (S)‖2‖PT◦(Z − Z∗)‖F
(T is the tangent cone of PSD matrices at Z)
≤‖PT (S)‖2‖Z − Z∗‖F = max
j {ã>j Sãj}‖Z − Z∗‖F
(ãj is the basis of the column space of Z )
≤ ‖Z − Z∗‖ (12) (from the definition of -FOSP)
On the other hand, from the definition of g̃, we have:
〈Z − Z∗,∇g̃(Z)〉 = ∑ ij (zij − z∗ij)g̃′ij(zij)
= ∑ ij (zij − z∗ij)2 ∑ k odd σ2kPk(zij) ∑ k odd σ2kkz k−1 ij
≥‖Z − Z∗‖2Fσ41 (13)
Here polynomial Pk(zij) ≡ (zkij − (z∗ij)k)/(z − z∗) is always positive for z 6= z∗ and k to be odd.
Therefore by comparing (12) and (13) we have ‖Z − Z∗‖F ≥ ‖Z − Z∗‖2Fσ41 , i.e. ‖Z − Z∗‖F ≤ O( ).
Proof of Theorem 3. From Theorem 31 from Ge et al. (2015), we know for small enough learning rate η, and arbitrary small , there exists large enough T , such that Algorithm 1 generates an output A(T ) that is sufficiently close to the second order stationary point for f . Or formally we have, Tr((A (T ))>XiA (T )) = yi, ‖(∇Af(A(T ))− ∑ i=1 λiXiA
(T )):,j‖2 ≤ min ‖Aj,:‖2, ∀j ∈ [k] Tr(B>DA∇ALf (A(T ), λ)[B]) ≥ − ‖B‖22, ∀B, s.t.Tr(B>XiA) = 0
Lf (A, λ) = f(A) − ∑d i=1 λi(Tr(A
>XiA) − yi). Let {ãi = A(T )ri}ki to form the basis of the column vector space of A(T ). Then the second line is a sufficient condition for the following: ‖ã>j (∇Af(A(T ))− ∑ i=1 λiXiA (T ))rj‖2 ≤ ,∀j ∈ [k].
Now with the concentration bound from Lemma 5, suppose our batch size m ≥ O(d5/ ), we have ‖∇Agn(A(T )) − ∇Af(A(T ))‖2 ≤ , and ‖DA∇Agn(A(T ))[B] − DA∇Af(A(T ))[B]‖2 ≤ ‖B‖2 for arbitrary B. Therefore again we get: Tr((A(T ))>XiA (T )) = yi ‖ã>j (∇Agn(A(T ))− ∑ i=1 λiXiA
(T ))rj‖2 ≤ 2 , ∀j ∈ [k] Tr(B>DA∇ALgm(A(T ), λ)[B]) ≥ −2 ‖B‖22, ∀B, s.t.Tr(B>XiA) = 0
Next we turn to the concentration bound from Lemma 4. Suppose we have when the sample size n ≥ O(d5/ 2 log2(1/δ)), ‖DA∇Ag(A)[B] − DA∇Agn(A)[B]‖2 ≤ O( ‖B‖2), and ‖∇g(A) − ∇gn(A)‖2 ≤ O( ) with probability 1 − δ. Therefore similarly we get A(T ) is an O( )-SOSP for g(A) = 12 ∥∥∑∞ i=0 σ 2 i ( (A∗(A∗)>)◦i − (AA>)◦i )∥∥2 F .
Now with Lemma 6 that connects the approximate stationary points, we have Z := A(T )(A(T ))> is also an -FOSP of g̃(Z) = 12 ∥∥∑∞ i=0 σ 2 i ( (Z∗)◦i − Z◦i )∥∥2 F .
Finally with Lemma 7, we get ‖Z − Z∗‖F ≤ O( ).

Review summaries:
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.