On the Anomalous Generalization of GANs
Jinchen Xuan Yunchang Yang Ze Yang Di He Liwei Wang

The integer cp-rank of 2 × 2 matrices
    Thomas Laffey, Helena Šmigoc
    December 11th, 2019; revised on July 2nd, 2021
==================================================


Generative models, especially Generative Adversarial Networks (GANs), have received significant attention recently. However, it has been observed that in terms of some attributes, e.g. the number of simple geometric primitives in an image, GANs are not able to learn the target distribution in practice. Motivated by this observation, we discover two specific problems of GANs leading to anomalous generalization behaviour, which we refer to as the sample insufficiency and the pixel-wise combination. For the first problem of sample insufficiency, we show theoretically and empirically that the batchsize of the training samples in practice may be insufficient for the discriminator to learn an accurate discrimination function. It could result in unstable training dynamics for the generator, leading to anomalous generalization. For the second problem of pixel-wise combination, we find that besides recognizing the positive training samples as real, under certain circumstances, the discriminator could be fooled to recognize the pixel-wise combinations (e.g. pixel-wise average) of the positive training samples as real. However, those combinations could be visually different from the real samples in the target distribution. With the fooled discriminator as reference, the generator would obtain biased supervision further, leading to the anomalous generalization behaviour. Additionally, in this paper, we propose methods to mitigate the anomalous generalization of GANs. Extensive experiments on benchmark show our proposed methods improve the FID score up to 30% on natural image dataset. 




§ INTRODUCTION

Generative Adversarial Networks (GANs) have great potential in modeling complex data distributions and have attracted significant attention recently. A great number of techniques <cit.> and architectures <cit.> have been developed to make the training of GANs more stable and to generate high fidelity, diverse images. The corresponding generated samples are authentic and difficult for human to distinguish from the real ones.

Despite these improvements, recent work <cit.> reported a surprising phenomenon of anomalous generalization of GANs on a geometry dataset, raising new questions about the generalization behaviour. By anomalous generalization it means that several seemingly easy attributes are shown to be learned poorly by GANs, including numerosity (number of objects) and color proportion, which are important for human perception. For example, as shown in Figure <ref>, for a geometric-object training dataset where the number of objects for each training image is fixed (e.g. every training image has exactly two rectangles), it is observed that most generated images after training have very different numbers of objects than the training images (e.g. rectangle numbers of most generated images are not two). Mathematically speaking, with regard to the number of objects, the learned distribution of GANs differs significantly from the target distribution, which fails to achieve the goal of modeling the target data distribution faithfully.

Several works have developed theories for GANs. The original work proves the convergence to
equilibrium under ideal conditions <cit.>. Further extensions include <cit.>.  <cit.> points out that GANs may not have good generalization when the discriminator has finite capacity, e.g., neural networks. But they show generalization occurs for GANs under the weak metric of neural net distance. Although these theories provide deep understandings, the generalization and the convergence of GANs as well as how to achieve it in practice are still open problems.




Motivated by this observation, we discover and investigate two specific problems of GANs, namely sample insufficiency and pixel-wise combination, which cause GANs to have anomalous generalization behaviour. Moreover, we propose methods to improve the generalization of GANs.

For the problem of sample insufficiency, we show theoretically and empirically that the batchsize in practice could be insufficient for GANs to model the target data distribution. As a typical setting of GANs, the discriminator learns to separate the fake data distribution of the generator from the real data distribution approximated by the training dataset. In practice, the discriminator learns such a separation function based on the mini-batches sampled from the training dataset and the generated samples of the generator. However, since the size of the mini-batch is much smaller than all the possible samples in the high-dimensional data distribution, the separation function of the discriminator learned based on the mini-batch samples could be noisy. With this noisy discriminator as reference, the generator would learn noisy generation function too and the training dynamics become unstable. As a result, GANs would have anomalous generalization behaviour.    

For the problem of pixel-wise combination, in some situations, we find that the positive training samples and their pixel-wise combinations (pixel-wise average or pixel-wise logical-and) are both recognized as real by the discriminator during training. However, the pixel-wise combinations of the positive training samples could have very different properties from the real samples themselves, indicating that the discriminator is unable to differentiate those seemingly easy attributes (e.g. number of objects). With this fooled discriminator as reference, the generator could be fooled further to generate those pixel-wise combinations of training samples, which may not belong to the target distribution. As a result, the data distribution learned by the generator could be very different from the target data distribution and the generalization of GANs becomes anomalous. 



To summarize, our contributions are:

    
  * We show that in certain circumstances the discriminator tends to recognize the pixel-wise combinations of the positive training samples as real, which could fool the generator to have anomalous generalization behaviour.
    
  * We demonstrate theoretically and empirically that the sample insufficiency in practice could result in unstable training dynamics and anomalous generalization of GANs.
    
  * We show that the anomalous generalization reported in <cit.> is caused by the two problems (sample insufficiency and pixel-wise combination). We then propose novel methods to mitigate anomalous generalization behaviour. Figure <ref> shows that our proposed methods improve the proportion of correct generated images by almost 80%. Our methods also improve the FID up to 30% on natural image datasets.



§ BACKGROUND



 §.§ Generative adversarial networks

In most cases of GANs, the generator learns to map a prior distribution (e.g. standard Gaussian) to a fake distribution to approximate the target real data distribution. The discriminator learns a function to separate the real and fake distributions. They define the following min-max game:

    min_Gmax_D𝔼_x∼ℙ_r[f_1(D(x))] + 𝔼_x∼ℙ_z[f_2(D(G(x)))]

where ℙ_r and ℙ_z denote the real and prior distributions respectively. f_1 and f_2 are the critic functions for the positive and negative training samples (e.g. f_1(x) = log(x), f_2(x) = log(1-x)). 




 §.§ Anomalous generalization behaviour of GANs

Some anomalous generalization behaviours of GANs have been observed recently. In <cit.>, several seemingly easy attributes are shown to be learned poorly by GANs, including numerosity (number of objects) and color proportion, which are important for human vision systems. The phenomenon shows that the learned distribution of the generator fails to approximate the target distribution, raising new questions about the training dynamics and generalization behaviour of GANs.



§ SAMPLE INSUFFICIENCY


In this section, we first discuss the problem of sample insufficiency in general in Section <ref>. Its empirical observation is shown in <ref>, followed by the theoretical analysis in Section <ref>.



 §.§ Sample insufficiency in the general training of GANs


 In the training of GANs, the generator learns to fake the target distribution. The discriminator learns to separate the fake distribution of the generator from the real data distribution. To learn a good separation function between the fake and the real distributions, the discriminator needs to have sufficient information of them. But in practice, such information of the distribution is provided by the positive or negative training samples in the mini-batch. Since the batchsize is often much smaller than the size of all possible data in the high-dimensional data distribution, the information is insufficient and the separation function of the discriminator learned based on the mini-batch samples is noisy. With this noisy discriminator as reference, the generator could also learn a noisy generation function and the training dynamics of GANs become unstable. The smaller the batchsize is, the more unstable the training dynamics are. Since the training of the generator is unstable and the learned generation function is noisy, it is difficult for the learned distribution to approximate the target distribution. As a result, the generalization of GANs would become anomalous. We will show both empirically and theoretically that the sample insufficiency leads to anomalous generalization behaviour of GANs in the following subsections.
 


 §.§ Empirical verification


We do experiments to show that the problem of sample insufficiency could lead GANs to anomalous generalization, both for geometric and natural image generation.



We establish a geometry dataset consist of 64 images (while the experiment also applies to larger size) that all images (32 by 32 with 0/255 binary pixel value) in it have exactly two rectangles (8 by 8). The prior distribution is the discrete uniform distribution. Size of its support set is the same as the dataset. More details can be found in Appendix <ref>. We compare the mini-batch gradient descent (MGD) with the full-batch gradient descent (FGD). The batchsize for MGD and FGD is 16 and 64 respectively.

As shown in Figure <ref> (middle), caused by the sample insufficiency, the training dynamics for the mini-batch gradient descent (MGD) are highly unstable. Both the gradient and the loss go up and down frequently, suggesting it is difficult for GANs to model the target distribution if trained with small batchsize. The instability is also observed for the images generated from certain latent codes, which are the inputs of the generator. As shown in Figure <ref> (left), the generated samples for the three randomly drawn latent codes of MGD (z_0^MGD,z_1^MGD,z_2^MGD) change frequently during training with anomalous images of false rectangle numbers. But for the full-batch gradient descent (FGD), where the sample insufficiency is avoided and the separation function of the discriminator between the real and fake data distributions can be learned accurately at each step, the loss and gradients are stable. The learned distribution converges smoothly to the target distribution in a short time. 

The problem of sample insufficiency is also observed to influence the natural image generation for datasets like CELEB-A <cit.>. As shown in Figure <ref> (right), after trained with the same amount of data, the FID score is better for the larger batchsize, where the problem of sample insufficiency is relatively less severe, than the smaller batchsize, where the sample insufficiency is more problematic. In brief, the experiments show that the sample insufficiency makes the training dynamics unstable, both for the discriminator and the generator. Since the training of the generator and the discriminator are unstable and the learned generation function is noisy, it is hard for the learned distribution to approximate the target distribution. As a result, the final generalization behaviour of GANs becomes anomalous. 



 §.§ Theoretical analysis: a WGAN model


In this subsection, we introduce a simple yet prototypical model which shows that the insufficient batchsize will result in unstable training dynamics and smaller batch leads to poorer performance than that of larger batch. As a result, the generalization of GANs would become anomalous when the batchsize is small.
    
Assume that the real data distribution is a d-dimensional multivariate normal distribution centered at the origin, N(0,𝐈_d). The latent distribution of the generator is p_𝐳∼ N(0,𝐈_d). The generator is defined as G_θ(x)=θ+x. The discriminator is a linear function D_w(x)=w^⊤x.

We consider the WGAN model <cit.>, whose value function is constructed using the Kantorovich-Rubinstein duality <cit.> as

    W(ℙ_θ_REAL, ℙ_θ)=sup _f_L≤ 1𝔼_x ∼ℙ_θ_REAL[f(x)]-𝔼_x ∼ℙ_θ[f(x)]

where f_L denotes the Lipschitz constant of the function f, namely, f_L=inf{L:f  is  L-Lipschitz}. And ℙ_θ_REAL denotes the real data distribution, ℙ_θ denotes the distribution of the generator G_θ, and the supremum is taken over all the linear functions f_w(x)=w^⊤x since the optimal classifier f^* is absolutely linear. And when f_w is a linear function, f_w_L=w, so

    W(ℙ_θ_REAL, ℙ_θ)   =sup _w≤ 1𝔼_x ∼ℙ_θ_REAL[f_w(x)]-𝔼_x ∼ℙ_θ[f_w(x)]
       =sup _w≤ 1 w^⊤(𝔼_x ∼ N(0,𝐈_d)x-𝔼_z ∼ N(0,𝐈_d)[x+θ])

The generator is trained to minimize W(ℙ_θ_REAL, ℙ_θ). Denote F(w,θ)=w^⊤(𝔼_x ∼ N(0,𝐈_d)x-(𝔼_y ∼ N(0,𝐈_d)y+θ)). When we use stochastic gradient descent, the training procedure can be described as

    w_t+1=w_t+η_t ∇_w F(w,θ_t)
    θ_t+1=θ_t-μ_t ∇_θ  F(w_t+1,θ)

where η_t and μ_t are the step size. We present our result for gradient flow <cit.>, i.e., gradient descent with infinitesimal time interval, whose behaviour can be described by the following differential equations:

    ( [  ẇ(t); θ̇(t) ])=   ( [ η_t ∇_w F(w(t),θ(t)); -μ_t∇_θ F(w(t),θ(t)) ])


(A detailed explanation of gradient flow and stochastic gradient flow is in Appendix A.) We will show that when the WGAN in (<ref>) is trained using stochastic gradient flow, the batchsize will impact the behaviour of the training dynamics. That is, compared with large batchsize (or even full batch), when the batchsize is small, the training dynamics of WGAN suffer from a large variance, thus more unstable. Theorem 1 tells us that when the WGAN model is trained using constant step size stochastic gradient flow, then the variance of the output will increase as t grows, and is of order Θ(1/m). Namely, the variance will be large if the batchsize is small.

[Variance of WGAN, constant step size]
Denote [θ_t]_i as the i-th component of the vector θ_t. Suppose we train the WGAN model in (<ref>) using constant step size stochastic gradient flow with batchsize m, then the parameter of the generator θ_t satisfies

    Var([θ_t]_i)=∫_0^t[e^sAΣ]_d+i_2^2 d s=Θ(1/m)

where 

    A=[    0 -I_d;  I_d    0 ],
    Σ=[ √(2/m)I_d         0;         0         0 ],
    e^sA=[  (coss)I_d -(sins)I_d;  (sins)I_d  (coss)I_d ],

and [e^sAΣ]_d+i is the (d+i)-th row of the matrix e^sAΣ ,



The proof is in Appendix B. The main idea is that due to the special dynamics of optimization of mini-max problems, the bias caused by the randomness of the batch sampling in each epoch will accumulate, which will lead to large variation after many steps of training. Note that although in traditional optimization problems the variance of SGD caused by the randomness of samples will not affect the convergence <cit.>, the variance will damage the convergence properties in GANs.

Next we consider the vanishing step size case, in which η_t=μ_t=1/t (without loss of generosity assume t≥ 1. This step size is commonly used in convex optimization in practical problems <cit.>. Theorem 2 shows that the problem still exists in such case, whose proof is in Appendix C.

[Variance of WGAN, vanishing step size]
Suppose we train the WGAN model in (<ref>) using 1/t step size stochastic gradient flow with batchsize m, then the parameter of the generator θ_t satisfies

    Var([θ_t]_i)=Θ(1/m)





Here we consider only the WGAN because it is usually more stable than typical GANs. We believe that other forms of GANs will have a similar problem caused by the insufficient batchsize.



Although our theoretical analysis only considers the effect of noise in distribution, the same reason also applies to the effect of other irrelevant features especially when the generator cannot learn the real data distribution perfectly.




§ PIXEL-WISE COMBINATION

In this section, We first discuss the problem of pixel-wise combination in Section <ref>, followed by the illustration on toy and real datasets in Section <ref>. Finally, we provide a theoretical analysis in Section <ref>.





 §.§ Pixel-wise combination in the general training of GANs


When GANs are trained on image datasets, we find that under certain situation pixel-wise combinations (e.g. pixel-wise average or pixel-wise logical-and) of the real samples could fool the discriminator, although the generated combinations could have inconsistent properties. e.g. the pixel-wise average of two animal images in CIFAR10 could be unrecognizable for human. Take a simple case for illustration, suppose the discriminator is a linear classifier, given two real images, the pixel-wise average of those two real images are likely to be predict as positive sample by the linear discriminator. Since those pixel-wise combinations are recognized as real by the discriminator, the generator correspondingly tends to generate them. Therefore, the generated images could be different from the expected ones and the generalization of GANs becomes anomalous.



 §.§ Illustration on toy and real datasets


We demonstrate the problem of pixel-wise combination, which leads GANs to anomalous generalization, by a toy dataset. Our training dataset only consists of two binary images (pixel value is 0 or 255), both of which have exactly three rectangles. The positions of the rectangles of the two images are different, as shown at upper left in Figure <ref>. The generated images during training are plotted and their statistics are analyzed. 

As shown at upper left of Figure <ref>, even when the training dataset consists of two images, there are a lot of unexpected anomalous generated samples. Both the two training images have exactly three rectangles. But many generated images have two rectangles or four rectangles. The generated images with three rectangles consist only a small part of all the generated images (Figure <ref> upper right solid red curve). Furthermore, the anomalous generated images are exactly the same as the pixel-wise combinations of the two training images. The anomalous generated images with two rectangles are actually the pixel-wise logical-and of the two training images. The images with four rectangles are actually the pixel-wise logical-or of the two training images. Also, the problem of the pixel-wise combination is observed for the discrimination function of the discriminator. As plotted as dash curves at upper right of Figure <ref>, during the training, the discriminator recognizes the pixel-wise combinations of the two positive training images as real (give high scores by the discrimination function), as well as the two positive training images themselves. With this fooled discriminator as reference, the generator is fooled further to generate unexpected samples. As a result, the learned data distribution could differ a lot from the target data distribution. 

Beyond the toy dataset, the problem of pixel-wise combination does exist in the training of GANs in practice. For the natural image dataset CELEB-A, some generated images are exactly the same as the pixel-wise averages of the training data (Figure <ref> bottom). Also, the pixel-wise average of certain structurally similar images could generate realistic samples (Figure <ref>). In brief, the experiments show that the problem of pixel-wise combination exists for GANs and makes it hard to model the target data distribution faithfully, which leads to anomalous generalization behaviour.



 §.§ Theoretical analysis



In this section we give a possible explanation to the problem of pixel-wise combination by a theoretical analysis. Note that this phenomenon is most remarkable on the geometric or the facial datasets. The samples in those datasets are structurally similar, namely, for a facial dataset, the eyes, noses and other features of the human faces appear at fixed positions in the images with high probability. So we assume that the l_2 distance between most positive training samples in the dataset is small. 

For the discriminator f(x), without loss of generosity, assume that f(x) > 0 if the sample x is classified as real. We make the following assumptions.

Assume that f is L-Lipschitz.
 

Assume that the discriminator classifies all the positive training samples as real with a large margin (i.e. there exists ϵ>0 such that for all the positive training samples x, f(x)>ϵ).

Most classifiers satisfy the Lipschitz condition (for example, the softmax classifier). Assumption 2 means that the discriminator classifies  the positive training samples as real with high confidence. Our theorem shows that under these assumptions, the pixel-wise convex combination of any two positive training samples will be classified as real with high probability. The proof is in Appendix D.


If the discriminator f(x) satisfies Assumption 1-2. Then for any two samples x_1 and x_2 in the training dataset satisfying x_1-x_2_2≤δ and any λ∈ (0,1), we have 

    f(λ x_1+(1-λ)x_2)≥max{f(x_1)-L(1-λ)δ,f(x_2)-Lλδ}

Moreover, if ϵ>Lδmin{λ,1-λ}, then f(λ x_1+(1-λ)x_2)>0.













§ FIXING THE ANOMALOUS GENERALIZATION OF GANS



In this section, we propose novel methods to mitigate the two problems. We present the Pixel-wise Combination Regularization (PCR) to mitigate the problem of pixel-wise combination in Section <ref>. For the problem of sample insufficiency, we present the Sample Correction (SC) in Section <ref>. The results show that the anomalous generalization for the geometric dataset is avoided entirely (Section <ref>). For the natural image dataset, the training modifications could improve the FID score up to 30% (Section <ref>).


 §.§ Approach




  
Pixel-wise Combination Regularization



For the training of vanilla GANs, the positive training samples for the update of the discriminator come from the training dataset and the negative training samples are generated by the generator. Since we think that the discriminator tends to recognize the pixel-wise combinations of the images in the training dataset as real even though they are not in the target distribution, we define a dataset:

    D_com = {x_0,x_1,...x_n-1| x_k = y_i⊕ y_j/2 y_i,y_j ∈ D_training i≠ j}

and use the images in D_com as additional negative training samples to restrict this tendency. The ⊕ in Eqn. <ref> is the pixel-wise combination operation, it could be the pixel-wise average or pixel-wise logical-and/or. The samples in D_com are the combinations of every two images in the training dataset. The loss term for training with the Pixel-wise Combination Regularization can be written as: 

    L = 𝔼_x∼ℙ_r[f_1(D(x))]_positive samples+ 1/2[𝔼_x∼ℙ_g[f_2(D(x))] + 𝔼_x∼ℙ_com[f_2(D(x))]]_negative samples

where ℙ_r, ℙ_g and ℙ_com are the data distributions approximated by the training data, the generator and D_com. In this way, the tendency to generate those combination images is restricted. We refer to this addition of the negative training samples for the training of the discriminator as Pixel-wise Combination Regularization (PCR).



  
Sample Correction

We introduce a general framework to mitigate the problem of sample insufficiency. We assume that to model the target distribution, the discriminator is required to separate accurately the real samples in the target data distribution from the others not in it, which the sample insufficiency makes it difficult to achieve. For that goal, the realistic samples in the negative training batch are not useful. Intuitively, if the realistic samples appear in both the positive and the negative training batches, it would be ambiguous for the discriminator to learn the correct separation function. Therefore, we replace the realistic samples in the negative training batch with less realistic ones by a certain pre-defined measure of reality. In this way, the discriminator could efficiently learn an accurate separation function with limited batchsize. The Sample Correction approach is a general framework and the measure of reality could differ for different datasets. We present our experiments on the geometry and the CELEB-A datasets as examples in the next subsections.


 §.§ Experimental results on geometric dataset


As shown before, caused by the two problems, when trained on a geometry dataset where all the training images have exactly two rectangles, there would be a lot of anomalous generated samples with different number of rectangles. We use the two proposed methods to mitigate this anomalous generalization. We do experiments to verify the effects of our methods. The training dataset consists of 25600 binary images, all of which have exactly two rectangles. For the Pixel-wise Combination Regularization (PCR), the pixel-wise logical-and/or of the positive training images are precomputed (details in Appendix <ref>). They are used as additional negative training samples. For the Sample Correction (SC), the generated realistic samples in the negative training batch of the discriminator are discarded. The realistic samples are those with exactly two rectangles, the same as the positive training samples. 

As shown in Figure <ref> (right), compared to the vanilla approach, the SC approach (SC) almost eliminates the anomalous generalization and the proportion of correct images (rectangle number is 2) goes up to 97%. The Pixel-wise Combination Regularization (PCR) approach also improves the proportion but is stuck at 70%. We think this is caused by the still existence of the problem of sample insufﬁciency. Combining these two methods, the SC+PCR approach converges to 99%, much more quickly than other approaches, showing the existences of the two problems and the effects of our methods.


 §.§ Experimental results on natural image dataset



We also evaluate the effect of the proposed Pixel-wise Combination Regularization and Sample Correction method on natural image data, where the performances are measured by the FID score. 

For the pixel-wise combination, the pixel-wise averages of the training data are computed simultaneously at each training step of the discriminator. They are used as additional negative training samples. The size of the additional negative training samples is the same as the size of the negative training samples from the generator. The results with the Pixel-wise Combination Regularization (denoted as PCR) are compared with those of the vanilla training based on three popular GANs architectures WGAN-GP, LSGAN and SAGAN <cit.>. Three natural image datasets are involved: CIFAR10, CELEB-A and M-IMAGENET <cit.>. M-IMAGETNET is the validation set of the IMAGENET dataset. We train the network unsupervisedly with the Adam optimizer (α = .0002, β_1 = .5, β_2 = .9). As shown in Table <ref>, the performances improve in most cases after applying the Pixel-wise Combination Regularization. The FID scores of the baselines are consistent with that reported in <cit.>. For WGANGP trained on CIFAR10, the achieved best FID score improves up to 30%, showing the potentials of our regularization method. Interestingly, the improvements are more remarkable for the CIFAR10 and M-IMAGENET than the CELEB-A dataset. We hypothesize this is because the objects in CELEB-A tend to appear at regular or fixed positions. Therefore, the average of real images is likely to give a data point in the target data manifold. For example, it is very possible that the average of two human face images is still a realistic human face image (data in CELEB-A). But it is less possible for the average of images of a car and a dog to be a realistic image (data in CIFAR10).





For the Sample Correction method. We randomly select a small portion of the images as training data (M-CELEB-A and M-CIFAR). Dataset size is kept small (e.g. 32) so that the learned data distribution could approximate the target data distribution well. The measure of reality of a sample in this case is the normalized minimum L_2 distance of the sample to all the training data (DIF, between 0 and 1). We train GANs in two different ways, namely Vanilla and Sample Correction. The latter approach differs in that the realistic samples in the negative batch (DIF less than 0.1) are replaced with less realistic ones. The batchsize is kept small to better demonstrate the problem of sample insufficiency (e.g. 2). As shown in Figure <ref>, the Sample Correction approach outperforms the vanilla one by a large margin. FID and DIF scores are both better during training. This is because for the Sample Correction approach, the problem of sample insufficiency is restricted and the separation function of the discriminator is more accurate. The improvements can also be found visually (Figure <ref> left). For the vanilla approach, some generated samples degenerate to noises. But the Sample Correction approach can generate real ones with authentic details.







































































§ CONCLUSION AND FUTURE WORK

In this paper, we discuss two specific problems of GANs, namely sample insufficiency and pixel-wise combination. We demonstrate that they make it difficult to model the target distribution and lead GANs to anomalous generalization. Specific methods are introduced to prevent them from misleading the generalization of GANs, which improve the performance. We hope the two specific problems and the methods to restrict them can help the future work to better understand the generalization behaviour of GANs.


iclr2020_conference





§ AN EXPLANATION OF GRADIENT FLOW AND STOCHASTIC GRADIENT FLOW

Gradient flows, or steepest descent curves, are a very classical topic in evolution equations: given a
functional F defined on ℝ^d, and we want to look for points x minimizing F (which is related to the statical equation ∇ F(x) = 0). To do this, we look, given an initial point x_0, for a curve starting at x_0 and trying to minimize F as fast as possible. Since the negative gradient direction is the steepest descent direction, we will solve equations of the form 

    x'(t) = -∇ F(x(t))).

On the curve of the solution of this equation (t,x(t)), when t increases, at every point x(t) the point goes along the negative gradient direction.

If we write down the discrete form of (14), it becomes

    x(t+δ t)-x(t) = -∇ F(x(t)))

which is the Euler method of the differential equation. And if we take δ t=1, we get the expression of gradient descent. So we can view the gradient flow as gradient descent of infinitesimal time interval.

And if we add a stepsize term in the equation, it becomes

    x'(t) = -η_t∇ F(x(t))

where η_t denotes the step size. And in the discrete form, it falls into the familiar gradient descent formula with step size {η_t}:

    x(t+1)-x(t)=-η_t∇ F(x(t))


In most machine learning problems, the function F can be written as F(x)=1/n∑_i=1^n f_i(x), and  compute the gradient of F exactly can be computationally exhaustive. So instead we often use an approximation of ∇ F (for example, we can randomly select i∈{1,...,n} and use ∇ f_i to approximate ∇ F). This can be described formally as follows. If ∇ F(x(t))=g(x(t))+𝔼Y, where Y is a random vector with distribution p(y), then we can sample Y_t∼ p and update x as

    x(t+1)-x(t)=-η_t (g(x(t))+Y_t)

Especially, if p is a Gaussian distribution with mean 0 and covariance matrix I_d, then (18) is equivalent to

    x(t+1)-x(t)=-η_t (g(x(t))+(W(t+1)-W(t)))

where W(t) is a Wiener process<cit.>. And this is the Euler-Maruyama scheme<cit.> of the following stochastic differential equation:

    dX_t=-η_tg(X_t)dt-η_tdW_t
    
    X_0=x_0

the solution, if exists, is a stochastic process {X_t=X(t,x_0)}. We call this solution the stochastic gradient flow of F at point x_0. And when we say that F is trained using stochastic gradient flow, we mean that the curve {x_t} is a sample path of {X_t=X(t,x_0)}. 

Finally, when we say that F is trained using stochastic gradient descent with batchsize m, we mean that for each t, we sample Y_t^1,...,Y_t^m ∼ p and update x as 

    x(t+1)-x(t)=-η_t (g(x(t))+1/m∑_i=1^m Y_t^i).

This is the Euler-Maruyama scheme of the following stochastic differential equation:

    dX_t^m=-η_tg(X^m_t)dt-η_t1/mdW_t
    
    X^m_0=x_0

And when we say that F is trained using stochastic gradient flow with batchsize m, we mean that the curve {x_t} is a sample path of {X^m_t=X^m(t,x_0)}. 



§ PROOF OF THEOREM 1



First we give a detailed description of the training dynamics of our model in Section <ref> using gradient flow. 

The framework of training the WGAN in Section <ref> is as follows. Denote F(w,θ)=w^⊤(𝔼_x ∼ N(0,𝐈_d)x-(𝔼_y ∼ N(0,𝐈_d)y+θ)). For each epoch t=1,2,..., given the parameter of the generator θ_t, the target of the discriminator is

    max_w≤ 1 F(w,θ_t)=w^⊤(𝔼_x ∼ N(0,𝐈_d)x-(𝔼_y ∼ N(0,𝐈_d)y+θ_t))

The gradient of w is 

    ∇_w F(w,θ_t)=𝔼_x ∼ N(0,𝐈_d)x-(𝔼_y ∼ N(0,𝐈_d)y+θ_t)
 
And for one-step gradient upscent the update of w is

    w_t+1=w_t+η_t ∇_w F(w,θ_t)

where η_t is the step size.

After w_t is updated to w_t+1, given the parameter of the discriminator w_t+1, the target of the generator becomes

    min_θ F(w_t+1,θ)=w_t+1^⊤(𝔼_x ∼ N(0,𝐈_d)x-(𝔼_y ∼ N(0,𝐈_d)y+θ))

And the gradient of θ is 

    ∇_θ F(w_t+1,θ)=-w_t+1.

For one-step gradient descent the update of θ is 

    θ_t+1=θ_t-μ_t ∇_θ  F(w_t+1,θ)


Now we consider the case when η_t and μ_t are constants, η_t=μ_t=C. Without loss of generality assume C=1. And when the time interval is infinitesimal, the discrete dynamics converge to the gradient flow with constant step size, which can be written in the form of ordinary differential equations (ODEs):

    ( [  ẇ(t); θ̇(t) ])=   ( [  ∇_w F(w(t),θ(t)); -∇_θ F(w(t),θ(t)) ])
    
    =   ( [ 𝔼_x ∼ N(0,𝐈_d)x-(𝔼_y ∼ N(0,𝐈_d)y+θ(t));                                  -w(t) ])


Under the full-batch condition, which means that 𝔼_x ∼ N(0,𝐈_d)x=0 and 𝔼_y ∼ N(0,𝐈_d)y=0 can be precisely calculated, the solution to the above ODEs is

    w_t=w_0 cost-θ_0sint
    θ_t=θ_0cost+w_0 sint

Notice that the solution implies that w_t≤w_0+θ_0, which means that the 1-Lipschitz condition on w in WGAN is automatically satisfied if w_0 and θ_0 are initialized sufficiently small. The parameters lie on a circle around the equilibrium point (0,0), which are stable though do not converge.

When the batchsize is m, which means that we randomly draw i.i.d. samples x^1_t,...,x^m_t∼ N(0,𝐈_d) and y^1_t,...,y^m_t∼ N(0,𝐈_d) and use the sample mean x̅^m,t=1/m∑_i=1^m x^i_t and y̅^m,t=1/m∑_i=1^m y_t^i to estimate the true mean 𝔼_x ∼ N(0,𝐈_d)x and 𝔼_y ∼ N(0,𝐈_d)y, the gradients become ∇_w F=x̅^m,t-y̅^m,t -θ and ∇_θ F=-w. Since x^1_t,...,x^m_t and y^1_t,...,y^m_t are independent for different t, we have x̅^m,t,y̅^m,t∼ N(0,1/m𝐈_d) and they are independent for different t. So x̅^m,t-y̅^m,t∼ N(0,2/m𝐈_d). And the parameters w and θ satisfy the following stochastic differential equations:


    dw_t=-θ_t dt+√(2/m)dW_t
    
    dθ_t=w_t dt


where W_t is a d-dimensional standard Wiener process. Denote X_t=(w_t^⊤, θ_t^⊤)^⊤∈ℝ^2d, then X_t is a multidimensional OU process <cit.> with expectation 

    E[X(t) | X(0)]=e^tA  X(0)

and variance 

    Var[X(t) | X(0)]=∫_0^t e^tA e^-sAΣΣ^⊤(e^tA e^-sA)^⊤ d s

where 

    A=[    0 -I_d;  I_d    0 ]
    ,Σ=[ √(2/m)I_d         0;         0         0 ]

So e^tA=[  (cost)I_d -(sint)I_d;  (sint)I_d  (cost)I_d ] and 

    e^tAe^-sA=   [  (cost)I_d -(sint)I_d;  (sint)I_d  (cost)I_d ][  (cos-s)I_d -(sin-s)I_d;  (sin-s)I_d  (cos-s)I_d ]
    
    =   [  (cos(t-s))I_d -(sin(t-s))I_d;  (sin(t-s))I_d  (cos(t-s))I_d ]=e^(t-s)A

So the variance can be written as

    Var[X(t) | X(0)]=   ∫_0^t e^tA e^-sAΣΣ^⊤(e^tA e^-sA)^⊤ d s
    
    =   ∫_0^t e^(t-s)AΣΣ^⊤(e^(t-s)A)^⊤ d s
    
    =   ∫_t^0 e^(t-s)AΣΣ^⊤(e^(t-s)A)^⊤ d (t-s)
    
    =   ∫_0^t e^sAΣΣ^⊤(e^sA)^⊤ d s

And the variance of the i-th component of X(t) is

    Var[X(t) | X(0)]_ii
    =   ∫_0^t[e^sAΣ]_i [e^sAΣ]_i^⊤ d s
    
    =   ∫_0^t[e^sAΣ]_i_2^2 d s

where [e^sAΣ]_i denotes the i-th row of e^sAΣ. 

Since [e^sAΣ]_i_2^2≥ 0, for all t_1≤ t_2 we have Var[X(t_1) | X(0)]_ii≤Var[X(t_2) | X(0)]_ii. So the variance of the OU process will increase as t grows. And because the elements in Σ is of order Θ(1/√(m)), we have Var[X(t) | X(0)]=Θ(1/m). From the definition of X(t) we have Var([θ_t]_i)=Var[X(t)|X(0)]_d+i,d+i=∫_0^t[e^sAΣ]_d+i_2^2 d s. Hence we complete our proof.




§ PROOF OF THEOREM 2



Now we consider the vanishing step size situation, namely η_t=μ_t=1/t. And when the time interval is infinitesimal, the discrete dynamics converge to the gradient flow which can be written in the form of ordinary differential equations (assume t≥ 1):

    ( [  ẇ(t); θ̇(t) ])=   ( [  1/t∇_w F(w(t),θ(t)); -1/t∇_θ F(w(t),θ(t)) ])
    
    =   ( [ 1/t(𝔼_x ∼ N(0,𝐈_d)x-(𝔼_y ∼ N(0,𝐈_d)y+θ(t)));                                    -1/tw(t) ])


Under the full-batch condition, which means that 𝔼_x ∼ N(0,𝐈_d)x=0 and 𝔼_y ∼ N(0,𝐈_d)y=0 can be precisely calculated, the solution to the above ODEs is

    w_t=w_1 cos(ln t)+θ_1sin(ln t)
    θ_t=w_1sin(ln t)-θ_1cos(ln t)

Notice that the solution implies that w_t≤w_1+θ_1, which means that the 1-Lipschitz condition on w in WGAN is automatically satisfied if w_0 and θ_0 are initialized sufficiently small. The parameters lie on a circle around the equilibrium point (0,0), which are stable though do not converge.

When the batchsize is m, which means that we randomly draw i.i.d. samples x^1_t,...,x^m_t∼ N(0,𝐈_d) and y^1_t,...,y^m_t∼ N(0,𝐈_d) and use the sample mean x̅^m,t=1/m∑_i=1^m x^i_t and y̅^m,t=1/m∑_i=1^m y_t^i to estimate the true mean 𝔼_x ∼ N(0,𝐈_d)x and 𝔼_y ∼ N(0,𝐈_d)y, the gradients become ∇_w F=x̅^m,t-y̅^m,t -θ and ∇_θ F=-w. Since x^1_t,...,x^m_t and y^1_t,...,y^m_t are independent for different t, we have x̅^m,t,y̅^m,t∼ N(0,1/m𝐈_d) and they are independent for different t. So x̅^m,t-y̅^m,t∼ N(0,2/m𝐈_d). And the parameters w and θ satisfy the following stochastic differential equations:


    dw_t=-1/tθ_t dt+1/t√(2/m)dW_t
    
    dθ_t=1/tw_t dt


where W_t is a d-dimensional standard Wiener process. Denote X_t=(w_t^⊤, θ_t^⊤)^⊤∈ℝ^2d, then again, X_t is a multidimensional OU process with expectation

    E[X(t) | X(1)]=(w_1^⊤cos(ln t)+θ_1^⊤sin(ln t),w_1^⊤sin(ln t)-θ_1^⊤cos(ln t))^⊤

and variance 

    Var[X(t) | X(1)]=∫_1^t e^a(t) e^-a(s)Σ(s) Σ(s)^⊤(e^a(t) e^-a(s))^⊤ d s

where 

    A(t)=[       0 -1/tI_d;  1/tI_d       0 ]
    ,Σ(t)=[ √(2)/√(m)tI_d             0;             0             0 ]

and Ã(t) is a primitive function to A(t)dt. For example, we take:

    Ã(t)=∫ A(t)=[         0 -(lnt)I_d;  (lnt)I_d         0 ]


So e^Ã(t)=[  (coslnt)I_d -(sinlnt)I_d;  (sinlnt)I_d  (coslnt)I_d ] and 

    e^Ã(t)e^-Ã(s)=   [  (coslnt)I_d -(sinlnt)I_d;  (sinlnt)I_d  (coslnt)I_d ][  (cos-lns)I_d -(sin-lns)I_d;  (sin-lns)I_d  (cos-lns)I_d ]
    
    =   [  (coslnt/s)I_d -(sinlnt/s)I_d;  (sinlnt/s)I_d  (coslnt/s)I_d ]
    
    =   [  (coslns/t)I_d  (sinlns/t)I_d; -(sinlns/t)I_d  (coslns/t)I_d ]
    
    =   e^Ã(s/t)^⊤

the variance of the i-th component of X(t) is

    Var[X(t) | X(0)]_ii=   ∫_1^t[e^Ã(t) e^-Ã(s)Σ(s)]_i^2_2  d s
    
    =   ∫_1^t[e^Ã(s/t)^⊤Σ(s)]_i^2_2 d s
    
    =   ∫_1^t[e^Ã(s/t)^⊤]_i Σ(s)^2_2 d s
    
    =   ∫_1^t1/m[e^Ã(s/t)^⊤]_i [ √(2)/tI_d         0;         0         0 ]^2_2 d s
    
    =   Θ(1/m)

From the definition of X(t) we have Var([θ_t]_i)=Var[X(t)|X(0)]_d+i,d+i=Θ(1/m). Hence we complete our proof of the second part.




§ PROOF OF THEOREM 3



Since f is L-Lipschitz, we have

    |f(λ x_1+(1-λ)x_2)-f(x_1)|≤    Lx_1-(λ x_1+(1-λ)x_2)
    
    =   L(1-λ)x_1-x_2≤ L(1-λ)δ


    |f(λ x_1+(1-λ)x_2)-f(x_2)|≤    Lx_2-(λ x_1+(1-λ)x_2)
    
    =   Lλx_1-x_2≤ Lλδ

So we have

    f(λ x_1+(1-λ)x_2)≥ f(x_1)-L(1-λ)δ

and

    f(λ x_1+(1-λ)x_2)≥ f(x_2)-Lλδ

Hence, f(λ x_1+(1-λ)x_2)≥max{f(x_1)-L(1-λ)δ,f(x_2)-Lλδ}. And the second result follows by simple calculation.





§ SAMPLE INSUFFICIENCY


We show more examples to demonstrate the problem of sample insufficiency of GANs. It can misguide the discriminator and then generator, causing finally generator to generate anomalous images. The training dataset consists images whose rectangle number is exactly 2. They are 32 by 32 single-channel image. All rectangles are 8 by 8. Anomalous generated images have different number of rectangles. The two training designs are compared. First one is mini-batch gradient descent (MGD), where the insufficient problem is severe and training is unstable, giving rise to anomalous images during whole training. Second is full-batch gradient descent (FGD), where the insufficient problem is negligible. Training for the second approach is stable, with few anomalous images generated. Generated images with certain individual latent codes are plotted. Images are grey single-channel but shown in color for visualization purpose.



§ AVOIDING ANOMALOUS GENERALIZATION ON GEOMETRY DATA


We introduce two problems to explain the anomalous generalization results reported in <cit.>. Further, we demonstrate the anomalous can be avoided by training modifications. We have three modified training methods extended from the Vanilla training: Sample Correction (SC), Pixel-wise Combination Regularization (PCR) and the SC + PCR. For SC, the negative training samples generated from generator are discarded before fed to discriminator for gradient descent. The samples with true rectangle number is discarded. The selection can be implemented efficiently by counting the number of rectangle using straight forward counting algorithm. For PCR approach, the pixel-wise averages of the training data (pixel-wise logic-and and logic-union) are precomputed. Specifically, the way we generate training geometry data can be utilized for this precomputation. To generate 2-number-rectangle training geometry data, we first randomly generate several 3-number-rectangle images. After that, for each 3-number-rectangle image, we randomly remove one rectangle out of the three. The remove is done twice for each 3-number-rectangle image. By this we get two different 2-number-rectangle images out of one 3-number-rectangle image. Because of this construction method, we could obtain the pixel-wisely average images easily, i.e. pixel-wise logic-or or logic-and, which are 3-number-rectangle or 1-number-rectangle respectively. These precomputed additional images are used as additional negative training samples for the PCR approach. All images are 32 by 32 with one channel. All rectangles are 8 by 8.

In experiments, SC and PCR can both improve the proportion of correct generated images. Combining the SC and PCR, the proportion goes to 100% quickly. We show there is no mode collapses for these three training modifications: SC, PCR and SC+PCR. We randomly draw 30 training images. For each sample, we find the closest image in 256000 generated samples. Results are shown in Figure <ref>. For three training designs extended from the Vanilla (SC, PCR and SC+PCR), most training images are represented by the learned distribution of the generator, meaning the high performance is achieved (up to 99% correct generated images) without mode collapse.




