Year: 2018

Abstract:
Generative neural networks map a standard, probability distribution to a complex high-dimensional distribution, which represents the real world data set. However, a determinate input distribution as well as a specific architecture of neural networks may impose limitations on capturing the diversity in the high dimensional target space. To resolve this difficulty, we propose a training framework that greedily produce a series of generative adversarial networks that incrementally capture the diversity of the target space. We show theoretically and empirically that our training algorithm converges to the theoretically optimal distribution, the projection of the real distribution onto the convex hull of the network’s distribution space.

heading: 1 INTRODUCTION
text: Generative Adversarial Nets (GAN) Goodfellow et al. (2014) is a framework of estimating generative models. The main idea Goodfellow (2017) is to train two target network models simultaneously, in which one, called the generator, aims to generate samples that resemble those from the data distribution, while the other, called the discriminator, aims to distinguish the samples by the generator from the real data. Naturally, this type of training framework admits a nice interpretation as a twoperson zero-sum game and interesting game theoretical properties, such as uniqueness of the optimal solution, have been derived Goodfellow et al. (2014). It is further proved that such adversarial process minimizes certain divergences, such as Shannon divergence, between the generated distribution and the data distribution.
Simply put, the goal of training a GAN is to search for a distribution in the range of the generator that best approximates the data distribution. The range is often defined by the input latent variable z and its specific architecture, i.e., Π = {G(z,θ),θ ∈ Θ}. When the range is general enough, one could possibly find the real data distribution. However, in practice, the range is usually insufficient to perfectly describe the real data, which is typically of high dimension. As a result, what we search for is in fact the I-projection Csiszár & Shields (2004) of the real data distribution on Π.
Consider two cases:
1. The range of the generator Π is convex (see figure 1(a)), or it is not convex but the projection of the real data distribution on Π’s convex hull (CONV Π) is in Π (see figure 1(b)).
2. The range of the generator is non-convex and the projection of the real data distribution in CONV Π is not in the range Π (see figure 1(c)).
In case 1, one can find the optimal distribution in Π to approximate real data set in CONV Π. But in case 2, using standard GANs with a single generator, one can only find the distribution in Π
that is nearest to the projection. It then makes sense to train multiple generators and use a convex combination of them to better approximate the data distribution (than using a single generator in the non-convex case (see figure 1(c))).
The above argument is based on the assumption that one could achieve global optimality by training, while this is not the case in general. When reaching a local optimal distribution, in order to improve performance, do we need to add more generators and restart training? In this paper, we put forward a sequential training procedure that adds generators one by one to improve the performance, without retraining the previously added generators. Our contributions can be summarized as follows.
• We derive an objective function tailored for such a incremental training process. The objective function takes both the real data distribution and the pre-learned distribution into consideration. We show that with this new objective, we actually maximize marginal contribution when adding a new generator. We also put forward an incremental training algorithm based on the new objective function.
• We prove that our algorithm always converges to the projection of real data distribution to the convex hull of the ranges of generators, which is the optimal solution with multiple generators. This property continues to hold in online settings where target distribution changes dynamically.
• Our experiments show that our algorithm can overcome the local optimal issue mentioned above. We perform experiments on a synthetic dataset as well as two real world datasets, e.g., CelebA and MNIST, and conclude that our algorithm could improve the mixture distribution even in the case where the range is not sufficient enough.
• Experiments also show that, compared with previous methods, our algorithm is fast and stable in reducing the divergence between mixture distribution and the real data.

heading: 1.1 RELATED WORKS
text: Recently, there have been intensive researches on improving the performance of generative adversarial neural networks. Two lines of works are closely related to our paper. They focus mainly on improving the discriminator and the generator respectively.

heading: 1.1.1 IMPROVING THE DISCRIMINATOR
text: The Unrolled GAN introduced by Metz et al. (2016) improves the discriminator by unrolling optimizing the objective during training, which stabilizes training and effectively reduces the mode collapse. D2GAN proposed by Nguyen et al. (2017) utilizes two discriminators to minimize the KL-divergence and the reverse KL-divergence respectively. It treats different modes more fairly, and thus avoids mode collapse. DFM introduced by Warde-Farley & Bengio (2016) brings a Denoising AutoEncoder (DAE) into the generator’s objective to minimize the reconstruction error in order to get more information from the target manifold. Mroueh et al. (2017) proposed McGan based on mean and covariance feature matching to stabilize the training of GANs. Finally, WGAN introduced by Arjovsky et al. (2017) employs the Wasserstein distance, which is a more appropriate measure of performance, and achieves more stable performance.
These works are different from ours since they focus on the discriminator by measuring the divergence between the generated data and the real data more precisely. However, our work fixes the discriminator and tries to enrich the expressiveness of the generator by combining multiple generators.

heading: 1.1.2 IMPROVING THE GENERATOR
text: Wang et al. (2016) proposes two methods to improve the training process. The first is selfensembling GANs, which assembles the generators from different epochs to stabilize training. The other is Cascade GAN, where the authors train new generator using the data points with highest values from the discriminator. These two methods are heuristic ways to improve training, but with no theoretical guarantee.
Hoang et al. (2017) and Ghosh et al. (2017) proposed the methods called MGAN and multi-agent GANs respectively. The former introduces a classifier into the discriminator to catch different
modes, while the later employ a new component into the generators’ objective to promote diversity. Arora et al. (2017) introduces a new metric on distributions and proposes a MIX+GAN to search for an equilibrium. But all these methods need to train the multiple generators simultaneously, and none of them can deal with the case when the training process reaches a local optima. Also, these models lack flexibility, in the sense that when one tries to change the number of generators, all the generators need to be retrained.
Another closely related work is Tolstikhin et al. (2017), in which the authors propose a method called AdaGAN, which is based on a robust reweighting scheme on the data set inspired from boosting. The idea is that the new generators should focus more on the previous bad training data. But AdaGAN and other boosting-like algorithms are based on the assumption that one generator could catch some modes precisely, which may not be reasonable since the generator always learns to generate the average samples among the real data set in order to obtain low divergence, especially when the generator’s range is under condition of Figure 1(c). In Section 5, we compare our algorithm with AdaGAN with different dataset.

heading: 2 PRELIMINARIES
text: A GAN Goodfellow et al. (2014) takes samples (a.k.a. latent variables z) from a simple and standard distribution as its input and generates samples in a high dimensional space to approximate the target distribution. This is done by training a generative neural network and an auxiliary discriminative neural network alternatively. An f-GAN Nowozin et al. (2016) generalizes the adversarial training as minimizing the f-divergence between the real data distribution and the generated distribution, defined as Df (p‖q) = ∫ x q(x)f ( p(x) q(x) ) dx. A GAN is a special f-GAN that minimizes the JensenShannon divergence. The general objective function of an f-GAN can be defined as follows: min θ max ξ F (θ, ξ) = Ex∼pdata [Tξ(x)] + Ex∼pθ [−f∗(Tξ(x))].
Here f∗ is the conjugate function of f in f-divergence; T represents a neural network regarded as the corresponding discriminator; finally, θ and ξ denote the parameters of the generator and the discriminator, respectively.

heading: 2.1 GENERATOR GROUP
text: The adversarial training method proposed by Goodfellow et al. (2014) is playing a minimax game between the generator and the discriminator. Such a method can be caught in local optima and thus is undesirable (e.g., mode collapse).
In this paper we propose a novel framework to train multiple generators sequentially: We maintain a group of generators (empty at the beginning) as well as their corresponding weights, then add new generators into the group one by one and rebalance the weights. In particular, only the newly added generator at each step is trained. The purpose here is to augment the capacity of the group of generators and mitigate the local optima issue.
Define the distribution range of a generator as Π = {p | p = G(z,θ),θ ∈ Θ}, i.e., the set of distributions that the generator can produce with different parameter θ. The distribution range is determined by the distribution of input z and the architecture of the generative network. Define a generator group as G = {G1, G2, , . . . , Gn} , where Gi is the generator added in step i. We associate each generator with a weight ωi > 0. Then the mixed distribution of the group is: ppre(x) = 1Φn ∑n i=1 ωipi(x),
where pi(x) = Gi(z) and Φn = ∑n i=1 ωi is the sum of weights. When a new generator Gn+1 joins in the group G, the group becomes G′ = G ∪ {Gn+1} and the mixed distribution becomes
pnow(x) = 1
Φn+1 n+1∑ i=1 ωipi(x) = 1 Φn+1 (Φn · ppre(x) + ωn+1 · pn+1(x)) .

heading: 3 AN INCREMENTAL TRAINING FRAMEWORK
text: In this section, we describe how we use a generator group to improve the performance and tackle the local optima issue mentioned previously. To train such a generator group, we propose an incremental
training algorithm (algorithm 1) adding generators to the group sequentially. In algorithm 1, we use
Algorithm 1 Incremental Training Algorithm Predetermined: preal, pz, Gi(z), i ∈ {1, 2, . . . , N} ωi, i ∈ {1, 2, . . . , N + 1} Input preal, pz, ωi, i > 0. Output generator group G. Initialize i← 1. repeat
Build and initialize generator Gi using the same network structure. Set target distribution for Gi to be ptarget = Φi·preal− ∑ j<i ωjpj
ωi .
Train Gi to minimize D(ptarget, pi). i← i+ 1.
until Convergence
D(·, ·) to denote the “distance” between two distributions, which can be any divergence (e.g., fdivergence or Wasserstein distance) or a general norm.
The key step in algorithm 1 is the choice of the target distribution for training Gi. Ideally, if D(ptarget, pi) = 0, then we have pi = ptarget. In this case, preal = 1Φi ∑i j=1 ωjpj and after adding Gi, the generator group G can perfectly produce the desired distribution preal. However, in general, we have D(ptarget, pi) 6= 0 and our algorithm proceeds in a greedy fashion, i.e., it always maximizes the marginal contribution of Gi to the generator group G. We devote the rest of this section to proving the above statement.

heading: 3.1 MARGINAL CONTRIBUTION MAXIMIZATION AT EACH ROUND
text: In algorithm 1, we use different loss functions for each generators. The marginal contribution of the (N + 1)-th generator is as follows when we adopt f-divergence as the distance measure:
V (GN+1) = Df (ppre||preal)−Df (pnow||preal) = ∫ x preal [ f ( ppre preal ) − f ( pnow preal )] dx (1)
To get a better approximation to the real distribution, we fix the existing generators in the group and tune the parameters of the new generator to minimize the distance between the new group and the real distribution. In fact, this is equivalent to maximizing the marginal contribution of the new generator V (GN+1) by selecting GN+1 = argmaxG′N+1V (G ′ N+1). Formally,
Proposition 1. For any distribution preal and any existing generator groupG = (G1, G2, . . . , GN ), the optimal target distribution p∗N+1 for a new generator GN+1 to join the group G is
p∗N+1(x) =
[ ΦN+1 · preal(x)− ΦN · ppre(x)
ωN+1
]+ , where[·]+ = max{·, 0}
.
To show this, we first introduce the χ2-divergence. Definition 1 (χ2-divergence). The χ2-divergence between distribution p and q is: Dχ2(p||q) =∫ x (p(x)−q(x))2 q(x) dx. Note that χ
2-divergence is a special case of the f-divergence: Dχ2(p||q) = Df (p||q), when f(u) = (u− 1)2
In fact, with some mild assumptions on f , the f -divergence is well-approximated by χ2-divergence when p and q are close. The following lemma can be obtained via Taylor expansion Csiszár & Shields (2004). Lemma 1. For any f-divergence with f(u), if f(u) is twice differentiable at u = 1 and f ′′(1) > 0, then for any q and p close to q we have: Df (p||q) ∼ f ′′(1) 2 Dχ2(p||q).
Proof of proposition 1. We rewrite the objective function equation 1 for χ2-divergence:
V (GN+1) = ∫ x preal [ f ( ppre preal ) − f ( pnow preal )] dx = ∫ x (preal − ppre)2 − (preal − pnow)2 preal dx.
Algorithm 2 Training GN+1 by Gradient Descent
Input: preal, pz , η, ωN+1 and Gi(·,θi), ωi, i ∈ {1, 2, . . . , N} repeat
Sample {xjreal} from preal Sample {zj} from pz for i = 1 to N do
Obtain samples by Gi(zj ,θi) as {xjGi} in Group G
end for Generate samples {xjgen} by GN+1 Update ξt+1 = ξt + η∇ξF (θtN+1, ξt) Update θt+1N+1 = θ t N+1−η∇θF (θtN+1, ξt)
until Convergence Output: GN+1(·,θN+1) Figure 2: A framework for training GN+1
Based on the former definition, we obtain V (GN+1) = ∫ x ωN+1·[−ωN+1·p2N+1+A·pN+1+B] (ΦN+1)2preal
dx, where A = 2(ΦN+1 · preal − ΦN · ppre) and B = (ΦN+1 + ΦN )p2pre − 2ΦN+1 · ppre · preal. To maximize the quadratic function V (GN+1), we have p∗N+1 = [A/2ωN+1]
+, which concludes the proof.
3.2 ALGORITHMS TO TRAIN Gi
According to algorithm 1, in each round, a new generator GN+1 is added and the loss function is set to be D(ptarget, pN+1). Therefore, when training each generator Gi, the target distribution only depends on the real distribution and the previous generators in G. In particular, both of them are already known (figure 2).
To minimizeD(ptarget, pGN+1), we conduct adversarial training by using an auxiliary discriminator T: F (θ, ξ) = Ex∼ptarget [Tξ(x)] + Ex∼pθ [−f∗(Tξ(x))], where by the linearity of expectation:
Ex∼ptarget [Tξ(x)] = {ΦN+1Ex∼preal [Tξ(x)]− ΦNEx∼ppre [Tξ(x)]}
ωN+1
= {ΦN+1Ex∼preal [Tξ(x)]−
∑N i=1 ωi · Ex∼pi [Tξ(x)]}
ωN+1 .
Based on these, we propose an incremental training algorithm for GN+1 as algorithm 2.

heading: 4 THEORETICAL ANALYSES
text: In this section, we show that although our framework which trains each generator in a greedy way, the output distribution of the generator group will always converge. Furthermore, the converged distribution is the closest one to the target distribution among the set of all possible distributions that a group of generators can produce (i.e., the optimal one within the distribution range of the group of generators).
Recall our notation that the distribution range of a generator is Π. By taking a convex combination of multiple generators (with the same architecture), the set of all possible output distributions becomes the convex hull of Π: CONV Π = {p(x) | p(x) = 1ΦN ∑N i=1 ωipi(x)}, where ωi > 0 is the weight of the i-th generator, pi(x) = Gi(z), 1 ≤ i ≤ N , and Gi represent the generative neural networks with the same architecture but different parameters. One can consider the parameters ωiΦN as the probability of choosing the i-th generator as the final output.

heading: 4.1 CONVERGENCE ANALYSIS
text: Our algorithm greedily optimizes each GN+1 to minimize D(ptarget, pGN+1). By the Pinsker’s inequality, the total variation distance between ptarget and pGN+1 is upper bounded by√ D(ptarget, pGN+1)/2 and we can easily extend it to χ
2-divergence by DKL(p||q) ≤ Dχ2(p||q) + 0.42. In other words, while greedily optimizing each GN+1, the distance between ptarget and pGN+1 is also approximately minimized. Hence it is reasonable to assume that for each GN+1, its distance to ptarget is approximately minimized with some tolerance ≥ 0, i.e., ‖pGN+1−ptarget‖ ≤ inf ‖p− ptarget‖+ . Under such an assumption, our algorithm approximately converges to the the optimal distribution in CONV Π: Proposition 2. For any Π that is connected and bounded, algorithm 2 approximately converges to the optimal distribution within the closure of the convex hull CONV Π of Π.
To simplify the argument, we fix each ωi to be 1 and embed the discrete probability distributions into a Hilbert space. In this case, each GN+1 approximately minimizes the distance to ptarget = (N + 1)preal − ∑N i=1 pGi can be formalized as:
‖pGN+1 − ptarget‖ ≤ infp∈Π ‖p− ptarget‖+ ,
and our algorithm approximately converges to the optimal distribution in CONV Π if as N →∞, ‖ 1N ∑N i=1 pGN − preal‖ ≤ infp∈CONV Π ‖p− preal‖+ .
Then proposition 2 is implied by the following lemma. Lemma 2. Consider a connected and bounded subset Π of a Hilbert spaceH and any target ρ ∈ H. Let {p∗n}∞n=1 be a sequence of points in Π such that for ρtarget = (n+ 1)ρ− nTn,
‖p∗n+1 − ρtarget‖ ≤ inf p∈Π ‖p− ρtarget‖+ , (?)
where Tn = 1n ∑n i=1 p ∗ n and ≥ 0 is a constant. Then for any δ > 0, there exists N > 0 such that
∀n > N, ‖Tn − ρ‖ ≤ inf p∈CONV Π ‖p− ρ‖+ (1 + δ) .
Corollary 1. With the finite change of target distribution, algorithm 2 can converge to the new optimal distribution within CONV Π.
Due to the space limit, we send the proof to the appendix.
Based on corollary 1, regardless the change of target distribution, as long as it is an finite variation, algorithm 2 can converge to the projection of new target distribution. Due to the sequential nature and the above theoretical guarantee, our algorithm naturally generalizes the dynamic online settings.

heading: 5 EXPERIMENTS
text: We test our algorithm on a synthesized Gaussian distribution dataset and two well-known real world datasets: CelebA and MNIST, which are the complex high dimensional real world distributions.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Number of Generators
2
4
6
8
10
12
14
M ea n of
lo g[ D χ2 (p
re al ||p
no w )] Adagan
Incremental_gan Original_Gan
Figure 5: The mean log(Dχ2(preal||pnow)) of 30 repetition experiments . 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Number of Generators
2
4
6
8
10
12
14
M in im um
o f
lo g[ D χ2 (p
re al ||p
no w )] Adagan
Incremental_gan Original_Gan
Figure 6: The minimum log(Dχ2(preal||pnow)) of 30 repetition experiments .
We design the experiment to test our sequential training algorithm. The main purpose is not to demonstrate high quality results, e.g., high definition pictures, but to show that our algorithm can search for an appropriate distribution that significantly improved the performance of mixture distributions as the number of generators increase, especially when the generator’s range is rather limited. In all experiments, we use the Adam optimizer Kingma & Ba (2014) with learning rate of 5× 10−5, and β1 = 0.5, β2 = 0.9. Finally, we set weights ωi = 1 for convenience.
Metric. As the method mentioned in Nowozin et al. (2016), when we fix the generator, we can train an auxiliary neural network to maximize the derived lower bound to measure the divergence between the generated data and the real data, i.e., Df (P ||Q). Based on these theories, we import an auxiliary neural network to measure the performance of different methods. The architecture of the auxiliary neural network is the same as the discriminator used in each experiment. We train it for 50 epoches, which is enough to measure the differences. Then we take the mean value of the last 100 iterations as the final output.
Synthesized data. In this part, we design some experiments in R2 space. The dataset is sampled from 8 independent two-dimensional Gaussian distributions (i.e., the blue points in figure 3). The model is previously proposed by Metz et al. (2016).
Firstly, following the experiment designed in Metz et al. (2016) and Hoang et al. (2017), we choose the latent variable z in a high dimensional space as z ∼ N(0, I256), i.e., the distribution projection is likely to be in the generator’s range, which meets the condition of figure 1(a) or figure 1(b). In figure 3, the blue points are the real data while the corresponding colored number represents the data points generated by each generator respectively. As figure 3 shows, we train up to 4 generators to approximate the data distribution and the first generator tends to catch the data with high probability around the centre of each Gaussian. As the number of generators increasing, generated data tends to cover the data away from the centre in order to be complementary to previous mixture distributions and thus gains a considerable marginal profit. These results demonstrate our marginal maximization algorithm can promote the mixture distributions to cover the data with low probabilities.
Secondly, we reduce the dimension of z to 1, i.e., z ∼ N(0, 1) and simplify the corresponding network architecture, so that the condition of figure 1(c) is likely met. In this part, we compare our algorithm with the state of the art incremental training method AdaGAN Tolstikhin et al. (2017) and the baseline method Orignal GAN.1 We train up to 20 generators in each experiment with the same starting generator (i.e., identical first generator for each method), then measure the Dχ2(p||q) between real distribution and the generated mixed distribution. We repeat the experiment for 30 times to reduce the effect of random noises. Figure 5 and figure 6 illustrate the average and the best performance with different numbers of generators, respectively. According to the result, our algorithm approaches to preal faster than the other two methods and achieves the best performance among all three methods.
In summary, our algorithm outperforms the other two both in terms of the speed of converging to the real distribution and the quality of the final result under the case of figure 1(c).
MNIST. In this experiment, we run our algorithm on the MNIST dataset LeCun et al. (1998). We design this experiment to measure the performance of our algorithm for a more complex data distribution. We choose the latent variable as z ∼ N(0, 1) to limit the corresponding generator range and
1The only difference is the target distribution, for Original GAN, we train each generator with the real data distribution, i.e., preal, then make a convex combination of them.
use the Wasserstein distance to measure the gap between mixed distribution and the real dataset.2 Then we train up to 22 generators to approximate the real distribution and the result is showed in figure 4. Our algorithm outperforms the Original GAN but is inferior to the AdaGAN with the first 8 generators. As the number of generators increases, AdaGAN seems to run into a bottleneck while both our algorithm and the Original GAN gradually approximate to the real data distribution.
In order to analysis the convergence, we further train up to 100 generators with both our algorithm and the original GAN. In figure 7, the horizontal dash lines represent the minimum value of the Wasserstein distance for the two method respectively. As showed in figure, the distance gradually decrease with the number of generators increasing, and our algorithm is much faster to reduce the distance and can even obtain a better performance. More over, as we tends to investigate the property of each generator in the generators’ group, we measure the Wasserstein distance between distribution G(z,θ) and the real data, the experiment result is showed in figure 8 and the dash lines in figure 8 represent the mean value of the 100 generators. Interestingly, the result shows that, in each generator, original GAN tends to search a distribution in the distribution range that is closer to the real data distribution, while our algorithm is searching for a distribution that is complementary to the generators’ group (i.e., a huge decrease in the mixture condition in figure 7) even if its own performance is poor (i.e., a high distance in the in figure 8).
CelebA. We also conduct our experiment on the CelebA dataset Liu et al. (2015). As shown in figure 1, we start with an identical generator and train up to 6 generators using different methods. The measured Wasserstein distance between mixed distribution of Group G and the real-data distribution is showed in figure 1. In this experiment, we use the training method WGAN-GP proposed by Gulrajani et al. (2017). The experiment results indicates that our algorithm outperforms the other two methods after the second generator. It demonstrates the potential of our algorithm applying to real world datasets.

heading: 6 FUTURE WORK
text: We intend to further investigate the problem of how to accelerate the convergence via optimal generator weights, i.e., ωi. Moreover, by measuring the relativity between the current group G and the dynamically changing target distribution, we intend to apply our algorithm to online learning.

heading: A MISSING PROOFS
text: A.1 PROOF OF LEMMA 2
Proof of lemma 2. Without loss of generality, we can assume ρ = 0, since otherwise we can add an offset −ρ to the Hilbert spaceH. Denote dn = n‖Tn‖ = ‖ ∑n i=1 p ∗ i ‖. Then according to equation ?,
dn+1 = (n+ 1)‖Tn+1‖ ≤ inf p∈Π ‖p+ nTn‖+ .
Let p̂ ∈ Π be the point that minimizes the distance between −nTn and its projection p̂⊥ on line −nTn, i.e., p̂ = arg minp∈Π ‖p⊥ + nTn‖, where p⊥ = 〈p,nTn〉H ‖nTn‖2 · nTn. Then we can further bound dn+1 by ‖p̂+ nTn‖,
dn+1 − ≤ ‖p̂+ nTn‖ = √ ‖p̂− p̂⊥‖2 + ‖p̂⊥ + nTn‖2.
On one hand, since Tn ∈ CONV Π, p̂⊥ can be seen as the projection of p̂ on Tn as well, hence ‖p̂ − p̂⊥‖ ≤ ‖p̂ − Tn‖. Note that Π is bounded, therefore ‖p̂ − Tn‖ is bounded by the diameter of Π, denoted as d ≥ 0. On the other hand, suppose that p∗ is the point closest to ρ = 0 within CONV Π, i.e., p∗ = arg minp∈CONV Π ‖p‖. Since Π is connected, therefore the projection of Π on −nTn is the same with the projection of CONV Π. Hence,
‖p̂⊥ + nTn‖ ≤ ‖p∗⊥ + nTn‖ ≤ ‖p∗ + nTn‖ ≤ ‖p∗‖+ dn.
In other words,
dn+1 − ≤ √ d2 + (‖p∗‖+ dn)2.
If ‖p∗‖ = infp∈CONV Π ‖p‖ > 0, then we have dn = n‖Tn‖ ≥ n‖p∗‖. Hence
dn+1 ≤ + ‖p∗‖+ dn + d2/2(‖p∗‖+ dn) ≤ + ‖p∗‖+ dn + d2/2(n+ 1)‖p∗‖ ≤ (‖p∗‖+ )(n+ 1) + d2/2‖p∗‖ · ln(n+ 1).
Then for any δ > 0, let N be sufficiantly large such that lnNN ≤ 2δ ‖p ∗‖/d2, we have
‖Tn − ρ‖ = dn/n ≤ inf p∈CONV Π ‖p− ρ‖+ + δ .
Otherwise, ‖p∗‖ = 0 and dn+1 ≤ + √ d2 + d2n. Note that the upper bound is increasing in dn, hence ∀n > 0, dn ≤ d∗n for d∗n defined as follows:
d∗0 = 0, d ∗ n+1 = + √ d2 + d∗n 2.
For which, we can easily prove by induction that d∗n ≤ n + √ nd. Therefore ‖Tn‖ = dn ≤
+ d/ √ n, which immediately completes the proof.
A.2 PROOF OF COROLLARY 1
Proof of corollary 1. Without loss of generality, we assume the optimal projection of target distribution is changed from ρ to ρ′ after n0 iterations, where n0 ∈ R+ is a constant value. Then we can derive ‖Tn+n0 − ρ′‖ ≤ n·‖Tn−ρ′‖ n+n0 + n0·‖Tn0−ρ ′‖ n+n0
, where n ∈ R+ is the training iteration after change. Then based on lemma 2, we obtain lim
n→+∞ ‖Tn − ρ′‖ ≤ infp∈Π ‖p − ρ′‖ + . On the other side,
for a specific n0, ‖Tn0 − ρ′‖ ≤ ‖Tn0 − ρ‖ + ‖ρ − ρ′‖ is a bounded value if the variation of target distribution is limited. Finally, we can obtain lim
n→+∞ ‖Tn+n0 − ρ′‖ ≤ infp∈Π ‖p− ρ′‖+ , which concludes the proof.
A.3 THE GAP BETWEEN KL DISTANCE AND χ2 DISTANCE
Lemma 3. At worst case, DKL(p||q) ≤ Dχ2(p||q) + 0.42. Proof. According to f-divergence, we have Df (p||q) = ∫ x q(x) · f ( p(x) q(x) ) dx. For KL-divergence and χ2 -divergence, the corresponding f(t) are fKL(t) = t log(t) and fχ2(t) = (t−1)2 respectively. Import an auxiliary function as:
F (t) = fχ2(t)− fKL(t)
Then based on the monotonicity of F(t), we have F (t)min ≥ −0.42. DKL(p||q) = ∫ x p(x)fKL ( p(x) q(x) ) dx
≤ ∫ x p(x) ( fχ2 ( p(x) q(x) ) + 0.42 ) dx = Dχ2(p||q) + 0.42
which conclude the proof.

Review summaries:
In this work, the authors propose to use multiple generators to estimate the target distribution. Especially, it assumes the case that the range of generators is non-convex and the target distribution doesn't fall into it. To solve this issue, the multiple generators are convex combined to do better approximation and an incremental training process is proposed to train multiple generators one by one.