Title: UNDERSTANDING GANS: THE LQG SETTING

Abstract: Generative Adversarial Networks (GANs) have become a popular method to learn a probability model from data. Many GAN architectures with different optimization metrics have been introduced recently. Instead of proposing yet another architecture, this paper aims to provide an understanding of some of the basic issues surrounding GANs. First, we propose a natural way of specifying the loss function for GANs by drawing a connection with supervised learning. Second, we shed light on the generalization peformance of GANs through the analysis of a simple LQG setting: the generator is linear, the loss function is quadratic and the data is drawn from a Gaussian distribution. We show that in this setting: 1) the optimal GAN solution converges to population Principal Component Analysis (PCA) as the number of training samples increases; 2) the number of samples required scales exponentially with the dimension of the data; 3) the number of samples scales almost linearly if the discriminator is constrained to be quadratic. Thus, linear generators and quadratic discriminators provide a good balance for fast learning.

1. INTRODUCTION:

Learning a probability model from data is a fundamental problem in statistics and machine learning. Building off the success of deep learning methods, Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) have given this age-old problem a face-lift. In contrast to traditional methods of parameter fitting like maximum likelihood estimation, the GAN approach views the problem as a game between a generator whose goal is to generate fake samples that are close to the real data training samples and a discriminator whose goal is to distinguish between the real and fake samples. The generator and the discriminators are typically implemented by deep neural networks. GANs have achieved impressive performance in several domains (e.g., (Ledig et al., 2016; Reed et al., 2016) ). Since (Goodfellow et al., 2014) , many variations of GANs have been developed, including f -GAN (Nowozin et al., 2016) , MMD-GAN (Dziugaite et al., 2015; Li et al., 2015) , WGAN (Arjovsky et al., 2017) , improved WGAN (Gulrajani et al., 2017) , relaxed WGAN (Guo et al., 2017) , Least-Squares GAN (Mao et al., 2016) , Boundary equilibrium GAN (Berthelot et al., 2017) , etc. These GANs use different metrics in the optimization for training the generator and discriminator networks (Liu et al., 2017) .

The game theoretic formulation in GANs can be viewed as the dual of an optimization that minimizes a distance measure between the empirical distributions of the fake and real samples. In the population limit where there are infinite number of samples, this optimization minimizes the distance between the generated distribution and the true distribution from which the data is drawn. In the original GAN framework, this distance measure is the Jenson Shannon divergence. However, Arjovsky et al (Arjovsky et al., 2017) noted that this distance does not depend on the generated distribution whenever its dimension is smaller than that of the true distribution. In this typical case, the Jenson Shannon divergence does not serve as a useful criterion in choosing the appropriate generated distribution. To resolve this issue, (Arjovsky et al., 2017) proposed the Wasserstein GAN (WGAN) which uses the first-order Wasserstein distance instead of Jensen-Shannon divergence. This distance is meaningful even when the dimension of the generated distribution is less than the true distribution. Nevertheless there are many other distance measures that satisfy this criterion and it is not clear how to choose among them. This is responsible in part for the fact that there are so many different GAN architectures. In fact, there is currently some confusion in the literature even on the basic issue of how to specify the loss function for GANs. For example, while the "Wasserstein" in Wasserstein Figure 1 : Summary of main results in the LQG setting. The population optimal GAN solution is PCA when the discriminator is unconstrained and when the discriminator is constrained to be quadratic. But the convergence to the population optimal is exponentially faster under a quadratic constraint on the discriminator.

GAN refers to the use of Wasserstein distance in the distance measure between the generated and true distributions, the "Least Squares" in Least-Squares GAN (Mao et al., 2016) refers to the use of squared error in the discriminator optimization objective. These are two totally different types of objects. The situation with GANs is in contrast to that in supervised learning, where how the loss function is specified in the formulation is clear and quite universally accepted.

A central issue in any learning problem is generalization: how close a model learnt from a finite amount of data is to the true distribution. Or, in statistical terms, how fast is the rate of convergence of the learnt model to the true model as a function of number of samples? Arora et al (Arora et al., 2017) have recently studied this problem for GANs. They observed that for Wasserstein GAN, if there are no constraints on the generator or the discriminator, the number of samples required to converge scales exponentially in the data dimension. They then showed that if the discriminator is constrained to be in a parametric family, then one can achieve convergence almost linearly in the number of parameters in that family (Theorem 3.1 in (Arora et al., 2017) ). However, the convergence is no longer measured in the Wasserstein distance but in a new distance measure they defined (the neural network distance). The result is interesting as it highlights the role of the discriminator in generalization, but it is somewhat unsatisfactory in that the distance measure needs to be modified to tailor to the specific constraints on the discriminator. Moreover, the result requires the invention of (yet) another family of distance measures for GANs.

In this paper, we first argue that there is a natural way to specify the loss function for GANs, in an analogous way as in the supervised learning setup. The resulting optimal GAN minimizes a generalized loss-function dependent Wasserstein distance between the generated distribution and the true distribution, and the dual formulation of this generalized Wasserstein distance leads to a loss-function dependent discriminator architecture. To study the impact of the constraints on the generator and the discriminator on the generalization performance in this distance measure, we focus on the case when the true data distribution is Gaussian. In this case, a natural loss function to consider is quadratic, and a natural class of generators to consider is linear with a given rank k. In this setting, the optimal GAN minimizes the second-order Wasserstein distance between the generated distribution and the empirical data distribution among all linear generators of a given rank. We show the following results:

1 In the population limit as the number of data samples grow, the optimal generated distribution is the rank k Gaussian distribution retaining exactly the top k principal components of the true distribution, i.e. GAN performs PCA in the population limit.

the dimension. The constrained GAN simply performs empirical PCA, and in the case when the rank k of the generator is the same as the dimension of the data distribution, GAN is equivalent to maximum likelihood estimation of the underlying Gaussian model.

These results are summarized in Figure 1 . The GAN architecture with a linear generator and a quadratic discriminator is shown in Figure 4 . (Arora et al., 2017) observed that the number of samples required to generalize for GAN is exponential in the dimension of the data when there are no constraints on either the generator or the discriminator. (They proved the result for first-order Wasserstein distance but a similar result holds for second-order Wasserstein distance as well, see Lemma 2 in Section 3.) Result 2 above says that even constraining the generator drastically to be linear cannot escape this exponential scaling. Result 3 says that this exponential scaling is not due to statistical limitation, but much better inference can be obtained by constraining the discriminator appropriately. Similar to Theorem 3.1 in (Arora et al., 2017) , Result 3 points to the importance of constraining the discriminator. But there are two key differences. First, the convergence in Result 3 is with respect to the original (second-order) Wasserstein distance, not another distance measure tailored to the constraint on the discriminator. Thus, the original quadratic loss function is respected. Second, the population limit is the same as the PCA limit achieved without constraints on the discriminator. Thus, by imposing a discriminator constraint, the rate of convergence is drastically improved without sacrificing the limiting performance.

There is no such guarantee in (Arora et al., 2017) . Our results also provide concrete evidence that an appropriate balance between the classes of generators and discriminators, i.e. linear generators and quadratic discriminators, can provide fast training.

The Linear-Quadratic-Gaussian (LQG) setting, dating back to at least Gauss, has been widely used across many fields, including statistics, machine learning, control, signal processing and communication. It has resulted in celebrated successes such as linear regression, the Wiener filter, the Kalman filter, PCA, etc., and is often used to establish a baseline to understand more complex models. We believe it serves a similar role here for GANs1 . Indeed it allows us to make a clear connection between GAN and PCA, perhaps the most basic of unsupervised learning methods. Moreover, even in this simple setting, the generalization issues in GAN are non-trivial, and understanding them in this setting provides the foundation to tackle more complex data distributions and more complex generators and discriminators such as deep nets.

The rest of the paper is organized as follows. In Section 2, we discuss a formulation of the GAN problem for general loss functions. In Section 3, we specialize to the LQG setting and analyze the generalization performance of GAN. In Section 4, we analyze the performance of GAN under a quadratic constraint on the discriminator. In Section 5, we present some experimental results.

2. A GENERAL FORMULATION FOR GANS:

Let {y i } n i=1 be n observed data points in R d drawn i.i.d. from the distribution P Y . Let Q n Y be the empirical distribution of these observed samples. Moreover, let P X be a normal distribution N (0, I k ). GANs can be viewed as an optimization that minimizes a distance between the observed empirical distribution Q n Y and the generated distribution P g(X) . The population GAN optimization replaces Q n Y with P Y . The question we ask in this section is: what is a natural way of specifying a loss function for GANs and how it determines the distance?

2.1. WGAN REVISITED:

Let us start with the WGAN optimization (Arjovsky et al., 2017) :

EQUATION

where G is the set of generator functions, and the p-th order Wasserstein distance between distributions P Z1 and P Z2 is defined as (Villani, 2008) W p p (P Z1 , P Z2 ) := inf

EQUATION

where the minimization is over all joint distributions with marginals fixed. Replacing (2) in (1), the WGAN optimization can be re-written as

EQUATION

or equivalently:

EQUATION

where the minimization is over all joint distributions P X,Y with fixed marginals P X and P Y .

We now connect (4) to the supervised learning setup. In supervised learning, the joint distribution P X,Y is fixed and the goal is to learn a relationship between the feature variable represented by X ∈ R k , and the target variable represented by Y ∈ R d , according to the following optimization:

EQUATION

where is the loss function. Assuming the marginal distribution of X is the same in both optimizations ( 4) and ( 5), we can connect the two optimization problems by setting (y, y ) = y -y in optimization (5). Note that for every fixed P X,Y , the solution of the supervised learning problem (5) yields a predictor g which is a feasible solution to the WGAN optimization problem (4). Therefore, the WGAN optimization (3) can be re-interpreted as solving the easiest such supervised learning problem, over all possible joint distributions P X,Y with fixed P X and P Y .

2.2. FROM SUPERVISED TO UNSUPERVISED LEARNING:

GAN is a solution to an unsupervised learning problem. What we are establishing above is a general connection between supervised and unsupervised learning problems: a good predictor g learnt in a supervised learning problem can be used to generate samples of the target variable Y. Hence, to solve an unsupervised learning problem for Y with distribution P Y , one should solve the easiest supervised learning problem P X,Y with given marginal P Y (and P X , the randomness generating distribution). This is in contrast to the traditional view of the unsupervised learning problem as observing the feature variable X without the label Y . (Thus in this paper we break with tradition and use Y to denote data and X as randomness for the generator in stating the GAN problem.)

This connection between supervised and unsupervised learning leads to a natural way of specifying the loss function in GANs: we simply replace the 2 Euclidean norm in (3) with a general loss function :

EQUATION

The inner optimization is the optimal transport problem between distributions of g(X) and Y (Villani, 2008) with general cost . This is a linear programming problem for general cost, so there is always a dual formulation (the Kantorovich dual (Villani, 2008) ). The dual formulation can be interpreted as a generalized discriminator optimization problem for the cost . (For example, in the case of being the Euclidean norm, we get the WGAN architecture; see Figure 2(a) .) Hence, we propose (6) as a formulation of GANs for general loss functions.

2.3. QUADRATIC LOSS:

The most widely used loss function in supervised learning is the quadratic loss: (y, y ) = y -y 2 (squared Euclidean norm). Across many fields its use had led to many important discoveries. With the connection between supervised and unsupervised learning in mind, this loss function should be a prime choice to consider in GANs as well. This choice of the loss function leads to the quadratic GAN optimization:

EQUATION

Since Wasserstein distances are weakly continuous measures in the probability space (Villani, 2008) , similar to WGAN, the optimization of the quadratic GAN is well-defined even if k < d. The dual formulation (discriminator) for W 2 is shown in Figure 2(b) . Note that in this dual, the discriminator applies ψ to the real data and the convex conjugate ψ * to the generated (fake) data.

g(.) -Ψ(Y) Ψ(Y) Yє R d Xє R k Yє R d ^^+ WGAN Ψ:1-Lip (b) (a) g(.) -Ψ * (Y) -Ψ(Y) Yє R d Xє R k Yє R d ^^+ Quadratic GAN Ψ:convex

The empirical quadratic GAN optimization can be formulated by replacing P Y with the empirical distribution Q n Y of the data as follows: inf

EQUATION

Note that while in practice one generates fake samples from X, we will keep the notations simpler in this paper by assuming we can generate the exact distribution g(X), i.e. we can generate as many fake samples as we wish. Almost all our results can be extended to the case when we have finite number of samples from X comparable to the number of samples from Y .

For the rest of the paper, we will focus on the problem (8) for the particular case of Y Gaussian of dimension d, and g linear of rank k ≤ d. This is the LQG setting for GANs.

3 GANS UNDER THE LQG SETUP

3.1. THE POPULATION GAN OPTIMIZATION:

First, we analyze the population GAN optimization under the LQG setup. We have the following lemma:

Lemma 1 Let S be a k dimensional subspace in R d . Let Ŷ be a random variable whose support lies in S. Then, Ŷ * , the optimal solution of the optimization

EQUATION

is the projection of Y to S.

Proof 1 See Appendix B.2.

This Lemma holds even if P Y is a non-Gaussian distribution. However, P Ŷ * cannot be generated as g(X) when P X ∼ N (0, I k ) and g(.) is restricted to be linear.

Using Lemma 1 and under the LQG setup, we show that the optimal solution for the population GAN optimization is the same as the PCA solution. PCA is the most standard unsupervised learning approach (Jolliffe, 2002) . PCA computes an optimal linear mapping from Y to Ŷ under the rank constraint on the covariance matrix of Ŷ (K Ŷ ). We say Ŷ is the k-PCA solution of Y if K Ŷ is a rank k matrix whose top k eigenvalues and eigenvectors are the same as top k eigenvalues and eigenvectors of the covariance matrix of Y (K Y ).

Theorem 1 Let Y ∼ N (0, K Y ) where K Y is full-rank. Let X ∼ N (0, I k )

where k ≤ d. The optimal population GAN solution of optimization (7) under linear G is the k-PCA solution of Y .

Proof 2 See Appendix B.3.

Lemma 1 holds if we replace W 2 with W 1 . However, the conclusion of Theorem 1 is tied to the W 2 distance because the PCA optimization also considers the quadratic projection loss.

3.2. THE EMPIRICAL GAN OPTIMIZATION:

In reality, one solves the GAN optimization over the empirical distribution of the data Q n Y , not the population distribution P Y . Thus, it is important to analyze how close optimal empirical and population GAN solutions are in a given sample size n. This notion is captured in the generalization error of the GAN optimization, defined as follows:

Definition 1 (Generalization of GANs) Let n be the number of observed samples from Y . Let ĝ(.) and g * (.) be the optimal generators for empirical and population GANs respectively. Then,

EQUATION

is a random variable representing the excess error of ĝ over g * , evaluated on the true distribution. 

d G (P Y , Q n Y ) can

(P Y , Q n Y ) → 0 quickly as n → ∞. Before analyzing the convergence rate of d G (P Y , Q n Y )

for linear G, we characterize this rate for an unconstrained G. For an unconstrained G, the second term of ( 10) is zero (this can be seen using a space filling generator function (Cannon & Thurston, 1987) ). Moreover, P ĝ(X) can be arbitrarily close to Q n Y . Thus, we have

EQUATION

which goes to zero with high probability with the rate of O(n -2/d ).

The approach described for the unconstrained G corresponds to the memorization of the empirical distribution Q n Y using the trained model. Note that one can write

n -2 d = 2 -2 log(n) d .

Thus, to have a small W 2 2 (P Y , Q n Y ), the number of samples n should be exponentially large in d (Canas & Rosasco, 2012) . It is possible that for some distributions P Y , the convergence rate of

W 2 2 (P Y , Q n Y ) is much faster than O(n -2/d ).

For example, (Weed & Bach, 2017) shows that if P Y is clusterable (i.e., Y lies in a fixed number of separate balls with fixed radii), then the convergence of W 2 2 (P Y , Q n Y ) is fast. However, even in that case, one optimal strategy would be to memorize observed samples, which does not capture what GANs do.

In supervised learning, constraining the predictor to be from a small family improves generalization. A natural question is whether constraining the family of generator functions G can improve the generalization of GANs. In the LQG setting, we are constraining the generators to be linear. To simplify calculations, we assume that Y ∼ N (0, I d ) and d = k. Under these assumptions, the GAN optimization ( 8) can be re-written as

EQUATION

)

where K is the covariance matrix with the eigen decomposition K = UΣU t . The optimal population solution of this optimization is µ * pop = 0 and K * pop = I, which provides a zero Wasserstein loss.

Theorem 2 Let µ * n and K * n be optimal solutions for optimization (12). Then, µ * n → 0 with the rate of O(d/n) and Tr(Σ * n ) → d with the rate of O(n -2/d ).

Proof 3 See Appendix B.4.

It turns out that Tr(Σ * n ), which is a random variable, is strongly concentrated around its expectation. Thus, Theorem 2 indicates that there is a significant bias in GAN's estimation of the true distribution which translates to the slow convergence of the generalization error. Note that in the Wasserstein space, the empirical distribution Q n Y and the population distribution P Y are far from each other (the distance between them concentrates around n -2/d (Canas & Rosasco, 2012) ). Thus, if there exists another Gaussian distribution within the sphere around Q n Y with the radius of n -2/d , the Wasserstein-based learning method will converge to the wrong Gaussian distribution. This phenomenon causes a bias in estimating the true distribution.

Theorem 2 considers the regime where k = d. In practice, the dimension of the generated distribution is often much smaller than that of the true one (i.e., k d). In this case, GAN's convergence rate can be increased from O(n -2/d ) to O(n -2/k ). However, this faster convergence comes at the expense of the increased bias term of the excess error (the second term of ( 10)). The trade-off is favorable if Y is near low rank. Nevertheless even the convergence rate of O(n -2/k ) is still slow. In practice, however, GANs have demonstrated impressive performance. In the next section, we show that by suitably constraining the GAN optimization, the convergence rate can be improved exponentially.

4. GANS WITH CONSTRAINED DISCRIMINATORS:

In this section, first we review the min-max (dual) formulation of WGAN (Arjovsky et al., 2017) . Then, we characterize the min-max formulation of the quadratic GAN. Finally, we show that a properly constrained quadratic GAN achieves the empirical PCA solution, which converges to the population optimal with an exponentially faster rate of convergence compared to the case when the discriminator is unconstrained.

Using the Kantorovich duality (Villani, 2008) , the first-order Wasserstein distance W 1 (P Y , P g(X) ) can be written as the following optimization (Arjovsky et al., 2017) :

EQUATION

where the function ψ(.) is restricted to be 1-Lipschitz. This dual formulation of W 1 is then used in optimization (1) to implement WGAN in a min-max architecture similar to the one of the original GAN (Figure 2 ). In this architecture, ψ(.) is implemented by deep neural networks.

In a similar way, one can write the second-order Wasserstein distance W 2 2 (P Y , P g(X) ) as the following optimization (Villani, 2008) :

EQUATION

where ψ * (ŷ) := sup v (v t ŷ -ψ(v)) is the convex-conjugate of the function ψ(.). Similarly, this dual formulation of W 2 2 can be used to implement the quadratic GAN optimization (7) in a min-max architecture which can be interpreted as a game between optimizing two functions g(.) and ψ(.) (Figure 2 ).

The following lemma characterizes the optimal solution of optimization ( 14) (Chernozhukov et al., 2017) :

Lemma 3 Let P Y be absolutely continuous whose support contained in a convex set in R d . For a fixed g(.) ∈ G, let ψ opt be the optimal solution of optimization (14). This solution is unique. Moreover, we have

EQUATION

where dist = means matching distributions.

In the LQG setup, since g(X) is Gaussian, ψ opt is a linear function. Thus, without loss of generality, ψ(.) in the discriminator optimization can be constrained to ψ(y) = y t Ay/2 where A is positive semidefinite. Therefore, we have

W 2 2 P Y , P g(X) = E[ Y 2 ] + E[ g(X) 2 ] + 2 sup ψ(y)=y t Ay/2,A 0 -E [ψ(Y )] -E [ψ * (g(X))] (16) = Tr(K Y ) + Tr(K g(X) ) + sup A 0 -Tr(AK Y ) -Tr(A † K g(X) ),

where A † is the pseudo inverse of the matrix A.

Now let Ỹ be a random variable whose distribution matches the empirical distribution Q n Y . Similarly we can write:

W 2 2 (P Ỹ , P g(X) ) = E[ Ỹ 2 ] + E[ g(X) 2 ] + 2 sup ψ(.):convex -E ψ( Ỹ ) -E [ψ * (g(X))] . (17)

For W2 2 (P Ỹ , P g(X) ), however, we cannot restrict ψ to convex quadratic functions because Ỹ is a discrete variable while g(X) is Gaussian. Thus, Lemma 3 implies that ψ opt for (17) cannot be linear. Nevertheless, by constraining to quadratic discriminators, we obtain a lower bound:

EQUATION

= Tr( KY ) + Tr(K g(X) ) + sup

A 0 -Tr(A KY ) -Tr(A † K g(X) ) = W 2 2 (P Z , P g(X) ),

where KY = E[ Ỹ Ỹ t ] (the empirical covariance matrix) and Z ∼ N (0, KY ) 2 . Therefore, the empirical constrained quadratic GAN solves the following optimization:

EQUATION

Using Theorem 1, the optimal g(X) to this problem is the empirical PCA solution, i.e. keeping the top k principal components of the empirical covariance matrix.

Theorem 3 Under the LQG setup, the solution of the empirical constrained quadratic GAN optimization is equivalent to the empirical PCA.

Consider the case where d = k (the case k < d is similar). The second term in the generalization distance d G (P Y , Q n Y ) (10) is zero. Therefore, we have

EQUATION

)

The W 2 2 distance between two Gaussians depends only on the covariance matrices. More specifically:

EQUATION

)

Hence, the convergence of this quantity only depends on the convergence of the empirical covariance to the population covariance, together with smoothness property of this function of the covariance matrices. The convergence has been established to be at a quick rate of Õ( d/n) (Rippl et al., 2016) .

Finally, note that if one has a finite number of X samples (replacing P g(X) with Q g(X) ), the constrained quadratic GAN would still have a fast convergence rate because only the empirical covariance matrix of g(X) plays a role in its optimization which converges quickly to the population covariance matrix.

5. EXPERIMENTAL RESULTS:

For experiments, we generate n i.i.d. samples from P Y ∼ N (0, I d ), represented as Q n Y . We then fit a d dimensional Gaussian distribution N (µ, K) to Q n Y using two methods: Maximum Likelihood (ML) estimation, which computes the sample mean and the empirical covariance; and WGAN (Arjovsky et al., 2017) with an affine generator function. Note that according to Theorem 3, ML is equivalent to the constrained quadratic GAN (19) . Moreover, note that the WGAN implementation uses W 1 and not W 2 in its optimization. Although analyzing GANs with W 2 is more tractable than that of W 1 , in practice we do not expect a significant difference between their performance. Considering this and owing to the lack of an implementation of GANs with W 2 , we perform numerical experiments using the WGAN implementation. Details of the experiments can be found in Appendix A.

Let μ and K be the estimated mean and the covariance. For evaluation, we compute

EQUATION

which is the W 2 2 distance between N (0, I d ) and N μ, K (see Lemma 4 in Appendix B).

Figure 3 demonstrates the estimation error of the ML (constrained quadratic GAN) and WGAN methods for d = 5 and d = 10 and in different sample sizes. These figures are consistent with Theorem 2 and results of Section 3.2 which suggest that GAN's convergence can be slow owing to a bias in its optimal empirical solution with respect to the population one. Moreover, this figure shows that the convergence of the constrained quadratic GAN (ML) is fast. Finally, in our experimental results of Figure 3 , one should take into the consideration practical issues of the WGAN implementation such as the use of the stochastic gradient descent, convergence to bad locals, etc.

6. DISCUSSIONS:

From a broader perspective, the problem we addressed in this paper is that of finding a good generative model for data coming from a Gaussian ground-truth, Y ∼ N (µ, K). This is an age-old problem in statistics, and the baseline solution is using maximum likelihood estimation: one uses the data to estimate the mean and covariance matrix of the Gaussian distribution, i.e. the empirical mean μ and empirical covariance matrix K, and obtain a generative model Ŷ ∼ N (μ, K). And when there is a desire to do dimensionality reduction, one can have a low-rank generative Gaussian model retaining the top k principal components of K. This is the empirical PCA solution.

What we have shown in this paper is that there is a natural GAN architecture that can accomplish exactly these tasks (Figure 4 ).

While this is certainly a complicated way of performing maximum likelihood Gaussian estimation and PCA, we believe the result is interesting in several ways. First, it is not at all obvious that there is a natural GAN architecture that can accomplish this task. Since Gaussian modeling is a basic task, this is a good sanity check on GANs. Second, arriving at this GAN architecture requires us to make several advances in our understanding of GANs. We needed to find a general way to specify the loss function for GANs, and then specialize to the quadratic loss function for the Gaussian problem at hand. This led to the use of the second-order Wasserstein distance for the generator optimization, and to a general GAN architecture from the dual formulation of this optimization. We then needed to find a proper way to constrain the class of generators and the class of discriminators in a balanced way to achieve fast generalization. Indeed our goal was not to recover the maximum likelihood solution but to overcome the slow generalization when there are no constraints on the generator and the discriminator. That the final architecture with balanced generators and discriminators is also the maximum likelihood solution gives this story a satisfactory ending.

:

The number of samples required for convergence in (second-order) Wasserstein distance however scales exponentially with the dimension of the data distribution.

Under a further constraint that the discriminator is quadratic, GAN converges to the same population-optimal PCA limit, but with the number of samples scaling almost linearly with

The importance of baselines in machine learning was also expressed by Ben Recht (talk at Stanford, Oct 18

2017).

Note that by considering ψ(y) = y t Ay/2 + h t y where A 0, we would have obtained Z ∼ N μY , KY where μY is the sample mean. For simplicity, we ignore the affine terms.

Figures and Tables:

Figure 2: Dual (min-max) formulations of (a) WGAN, and (b) Quadratic GAN.

Generalization errors of constrained quadratic GAN (ML) and WGAN under the LQG setup.

Figure

be viewed as a distance between P Y and Q n Y which depends on G. To have a proper generalization property, one needs to have d G

Table content: <table/>

Peer review (iclr2018):
 *Paper summary* The paper considers GANs from a theoretical point of view. The authors approach GANs from the 2-Wasserstein point of view and provide several insights for a very specific setting. In my point of view, the main novel contribution of the paper is to notice the following fact: (*) It is well known that the 2-Wasserstein distance W2(PY,QY) between multivariate Gaussian PY and its empirical version QY scales as , i.e. converges very slow as the dimensionality of the space increases. In other words, QY is not such a good way to estimate PY in this setting. A somewhat better way is use a Gaussian distribution PZ with covariance matrix S computed as a sample covariance of QY. In this case W2(PY, PZ) scales as . The paper introduces this observation in a very strange way within the context of GANs. Moreover, I think the final conclusion of the paper (Eq. 19) has a mistake, which makes it hard to see why (*) has any relation to GANs at all. There are several other results presented in the paper regarding relation between PCA and the 2-Wasserstein minimization for Gaussian distributions (Lemma 1 & Theorem 1). This is indeed an interesting point, however the proof is almost trivial and I am not sure if this provides any significant contribution for the future research. Overall, I think the paper contains several novel ideas, but its structure requires a *significant* rework and in the current form it is not ready for being published. *Detailed comments* In the first part of the paper (Section 2) the authors propose to use the optimal transport distance Wc(PY, g(PX)) between the data distribution PY (or its empirical version QY) and the model as the objective for GAN optimization. This idea is not novel: WGAN [1] proposed (and successfully implemented) to minimize the particular case of W1 distance by going through the dual form, [2] proposed to approach any Wc using auto-encoder reformulation of the primal (and also shoed that [5] is doing exactly W2 minimization), and [3] proposed the same using Sinkhorn algorithm. So this point does not seem to be novel. The rest of the paper only considers 2-Wasserstein distance with Gaussian PY and Gaussian g(PX) (which I will abbreviate with R), which looks like an extremely limited scenario (and certainly has almost no connection to the applications of GANs). Section 3 first establishes a relation between PCA and minimizing 2-Wasserstein distance for Gaussian distributions (Lemma 1, Theorem 1). Then the authors show that if R minimizes W2(PY, R) and QR minimizes W2(QY, QR) then the excess loss W2(PY, QR) - W2(PY, R) approaches zero at the rate (both for linear and unconstrained generators). This result basically provides an upper bound showing that GANs need exponentially many samples to minimize W2 distance. I don*t find these results novel, as they already appeared in [4] with a matching lower bound for the case of Gaussians (Theorem B.1 in Appendix can be modified easily to show this). As the authors note in the conclusion of Section 3, these results have little to do with GANs, as GANs are known to learn quite quickly (which contradicts the theory of Section 3). Finally, in Section 4 the authors approach the same W2 problem from its dual form and notice that for the LQG model the optimal discriminator is quadratic. Based on this they reformulate the W2 minimization for LQG as the constrained optimization with respect to p.d. matrix A (Eq 16). The same conclusion does not work unfortunately for W2(QY, R), which is the real training objective of GANs. Theorem 3 shows that nevertheless, if we still constrain discriminator in the dual form of W2(QY, R) to be quadratic, the resulting soliton QR* performs the empirical PCA of Pn. This leads to the final conclusion of the paper, which I think contains a mistake. In Eq 19 the first equation, according to the definitions of the authors, reads where QR is trained to minimize min_R W2(QY, R) and PZ is as defined in (*) in the beginning of these notes. However, PZ is not the solution of min_R W2(QY, R) as the authors notice in the 2nd paragraph of page 8. Thus (**) is not true (at least, it is not proved in the current version of the text). PZ is a solution of min_R W2(QY, R) *where the discriminator is constrained to be quadratic*. This mismatch is especially strange, given the authors emphasize in the introduction that they provide bounds on divergences which are the same as used during the training (see 2nd paragraph on page 2) --- here the bound is on W2, but the empirical GAN actually does a regularized training (with constrained discriminator). Finally, I don*t think the experiments provide any convincing insights, because the authors use W1-minimization to illustrate properties of the W2. Essentially the authors say "we don*t have a way to perform W2 minimization, so we rather do the W1 minimization and assume that these two are kind of similar". * Other comments * (1) Discussion in Section 2.1 seems to never play a role in the paper. (2) Page 4: in p-Wasserstein distance, ||.|| does not need to be a Euclidean metric. It can be any metric. (3) Lemma 2 seems to repeat the result from (Canas and Rosasco, 2012) as later cited by authors on page 7? (4) It is not obvious how does Theorem 2 translate to the excess loss? (5) Section 4. I am wondering how exactly the authors are going to compute the conjugate of the discriminator, given the discriminator most likely is a deep neural network? [1] Arjovsky et al., Wasserstein GAN, 2017 [2] Bousquet et al, From optimal transport to generative modeling: the VEGAN cookbook, 2017 [3] Genevay et al., Learning Generative Models with Sinkhorn Divergences, 2017 [4] Arora et al, Generalization and equilibrium in GANs, 2017 [5] Makhazani et al., Adversarial Autoencoders, 2015