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):
 First of all, let me state this upfront: despite the sexy acronym "GAN" in the title, this paper does not provide any genuine understanding of GANs. Conceptually, GANs are an algorithmic instantiation of a classic idea in statistics, mamely minimum-distance estimation, originally introduced by Jacob Wolfowitz in 1957 (*). This provides the *min* part. The *max* part comes from considering distances that can be expressed as a supremum over a class of test functions. Again, this is not new -- for instance, empirical risk minimization, in both supervised and unsupervised learning, can be phrased as precisely such a minimax problem by casting the convergence analysis in terms of suprema of suitable empirical processes (see, e.g., "Empirical Processes in M-Estimation" by Sara Van De Geer). Moreover, even the minimax (and, more broadly, game-theoretic) criteria go back all the way to the foundational papers of Abraham Wald. Now, the conceptual innovation of GANs is that this minimax formulation can be turned into a zero-sum game played by two algorithmic architectures, the generator and the discriminator. The generator proposes a model (which is assumed to be easy to sample from) and generates a sample starting from a fixed instrumental distribution; the discriminator evaluates the current proposal against a class of test functions, which, again, are assumed to be easily computable, e.g., by a neural net. One can also argue that the essence of GANs is precisely the architectural constraints on both the generator and the discriminator that make their respective problems amenable to *differentiable* approaches, e.g., gradient descent/ascent with backpropagation. Without such a constraint, the saddle point is either trivial or reduces to finding a worst-case Bayes estimate, as classical statistical theory would predict. This paper essentially strips away the essence of GANs and considers a stylized minimum-distance estimation problem, where both the target and the instrumental distributions are Gaussian, and the *distance* between statistical models is the quadratic Wasserstein distance induced by the Euclidean norm. This, essentially, stacks the deck in favor of linear strategies, and it is not surprising at all that PCA emerges as the solution. It is very hard to see how any of this helps our understanding of either strengths or shortcomings of GANs (such as mode collapse or stability issues). Moreover, the discussion of supervised and unsupervised paradigms is utterly unconvincing, especially in light of the above comment on minimum-distance estimation underlying both of these paradigms. In either setting, a learning algorithm is obtained from the population version of the problem by substituting the empirical distribution of the observed data for the unknown population law. Additional minor comments on proper attribution and novelty of results: 1) Lemma 3 (structural result for optimal transport with L_2 Wasserstein cost) is not due to Chernozhukov et al., it is a classic result in the theory of optimal transportation, in various forms due to Brenier, McCann, and others -- cf., e.g., Chapters 2 and 3 of C. Villani, "Topics in Optimal Transportation." 2) The rate-distortion formulation with fixed input and output marginal in Appendix A, while interesting, is also not new. Precise characterizations in terms of optimal transport are available, see, e.g., N. Saldi, T. Linder, and S. Yuksel, "Randomized Quantization and Source Coding With Constrained Output Distribution," IEEE Transactions on Information Theory, vol. 61, no. 1., pp. 91-106, January 2015. (*) The method of Wolfowitz is not restricted to distance functions in the mathematical sense; it can work equally well with monotone functions of metrics -- e.g., the square of a metric.