Non-Asymptotic Error Bounds for Bidirectional GANs
Year: 2022

Abstract:
We derive nearly sharp bounds for the bidirectional GAN (BiGAN) estimation error under the Dudley distance between the latent joint distribution and the data joint distribution with appropriately specified architecture of the neural networks used in the model. To the best of our knowledge, this is the first theoretical guarantee for the bidirectional GAN learning approach. An appealing feature of our results is that they do not assume the reference and the data distributions to have the same dimensions or these distributions to have bounded support. These assumptions are commonly assumed in the existing convergence analysis of the unidirectional GANs but may not be satisfied in practice. Our results are also applicable to the Wasserstein bidirectional GAN if the target distribution is assumed to have a bounded support. To prove these results, we construct neural network functions that push forward an empirical distribution to another arbitrary empirical distribution on a possibly different-dimensional space. We also develop a novel decomposition of the integral probability metric for the error analysis of bidirectional GANs. These basic theoretical results are of independent interest and can be applied to other related learning problems. ∗Corresponding authors 35th Conference on Neural Information Processing Systems (NeurIPS 2021).

text: ∗Corresponding authors
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

heading: 1 Introduction
text: Generative adversarial networks (GAN) (Goodfellow et al., 2014) is an important approach to implicitly learning and sampling from high-dimensional complex distributions. GANs have been shown to achieve impressive performance in many machine learning tasks (Radford et al., 2016; Reed et al., 2016; Zhu et al., 2017; Karras et al., 2018, 2019; Brock et al., 2019). Several recent studies have generalized GANs to bidirectional generative learning, which learns an encoder mapping the data distribution to the reference distribution simultaneously together with the generator doing reversely. These studies include the adversarial autoencoder (AAE) (Makhzani et al., 2015), bidirectional GAN (BiGAN) (Donahue et al., 2016), adversarially learned inference (ALI) (Dumoulin et al., 2016), and bidirectional generative modeling using adversarial gradient estimation (AGES) (Shen et al., 2020). A common feature of these methods is that they generalize the basic adversarial training framework of the original GAN from unidirectional to bidirectional. Dumoulin et al. (2016) showed that BiGANs make use of the joint distribution of data and latent representations, which can better capture the information of data than the vanilla GANs. Comparing with the unidirectional GANs, the joint distribution matching in the training of bidirectional GANs alleviates mode dropping and encourages cycle consistency (Shen et al., 2020).
Several elegant and stimulating papers have analyzed the theoretical properties of unidirectional GANs. Arora et al. (2017) considered the generalization error of GANs under the neural net distance. Zhang et al. (2018) improved the generalization error bound in Arora et al. (2017). Liang (2020) studied the minimax optimal rates for learning distributions with empirical samples under Sobolev evaluation class and density class. The minimax rate is O(n−1/2 ∨ n−α+β/(2α+β)), where α and β are the regularity parameters for Sobolev density and evaluation class, respectively. Bai et al. (2019) analyzed the estimation error of GANs under the Wasserstein distance for a special class of distributions implemented by a generator, while the discriminator is designed to guarantee zero bias. Chen et al. (2020) studies the convergence properties of GANs when both the evaluation class and the target density class are Hölder classes and derived O(n−β/(2β+d) log2 n) bound, where d is the dimension of the data distribution and α and β are the regularity parameters for Hölder density and evaluation class, respectively. While impressive progresses have been made on the theoretical understanding of GANs, there are still some drawbacks in the existing results. For example,
(a) The reference distribution and the target data distribution are assumed to have the same dimension, which is not the actual setting for GAN training.
(b) The reference and the target data distributions are assumed to be supported on bounded sets. (c) The prefactors in the convergence rates may depend on the dimension d of the data distribution
exponentially.
In practice, GANs are usually trained using a reference distributions with a lower dimension than that of the target data distribution. Indeed, an important strength of GANs is that they can model low-dimensional latent structures via using a low-dimensional reference distribution. The bounded support assumption excludes some commonly used Gaussian distributions as the reference. Therefore, strictly speaking, the existing convergence analysis results do not apply to what have been done in practice. In addition, there has been no theoretical analysis of bidirectional GANs in the literature.

heading: 1.1 Contributions
text: We derive nearly sharp non-asymptotic bounds for the GAN estimation error under the Dudley distance between the reference joint distribution and the data joint distribution. To the best of our knowledge, this is the first result providing theoretical guarantees for bidirectional GAN estimation error rate. We do not assume that the reference and the target data distributions have the same dimension or these distributions have bounded support. Also, our results are applicable to the Wasserstein distance if the target data distribution is assumed to have a bounded support.
The main novel aspects of our work are as follows.
(1) We allow the dimension of the reference distribution to be different from the dimension of the target distribution, in particular, it can be much lower than that of the target distribution.
(2) We allow unbounded support for the reference distribution and the target distribution under mild conditions on the tail probabilities of the target distribution.
(3) We explicitly establish that the prefactors in the error bounds depend on the square root of the dimension of the target distribution. This is a significant improvement over the exponential dependence on d in the existing works.
Moreover, we develop a novel decomposition of integral probability metric for the error analysis of bidirectional GANs. We also show that the pushforward distribution of an empirical distribution based on neural networks can perfectly approximate another arbitrary empirical distribution as long as the number of discrete points are the same.
Notation We use σ to denote the ReLU activation function in neural networks, which is σ(x) = max{x, 0}, x ∈ R. We use I to denote the identity map. Without further indication, ‖ · ‖ represents theL2 norm. For any function g, let ‖g‖∞ = supx ‖g(x)‖. We use notationO(·) and Õ(·) to express the order of function slightly differently, where O(·) omits the universal constant independent of d while Õ(·) omits the constant depending on d. We use Bd2 (a) to denote the L2 ball in Rd with center at 0 and radius a. Let g#ν be the pushforward distribution of ν by function g in the sense that g#ν(A) = ν(g−1(A)) for any measurable set A. We use Ê to denote taking expectation with respect to the empirical distribution.

heading: 2 Bidirectional generative learning
text: We describe the setup of the bidirectional GAN estimation problem and present the assumptions we need in our analysis.

heading: 2.1 Bidirectional GAN estimators
text: Let µ be the target data distribution supported on Rd for d ≥ 1. Let ν be a reference distribution which is easy to sample from. We first consider the case when ν is supported on R, and then extend it to Rk, where k ≥ 1 can be different from d. Usually, k d in practical machine learning tasks such as image generation. The goal is to learn functions g : R → Rd and e : Rd → R such that g̃#ν = ẽ#µ, where g̃ := (g, I) and ẽ := (I, e), g̃#ν is the pushforward distribution of ν under g̃ and ẽ#µ is the pushforward distribution of µ under ẽ. We call g̃#ν the joint latent distribution or joint reference distribution and ẽ#µ the joint data distribution or joint target distribution. At the population level, the bidirectional GAN solves the minimax problem:
(g∗, e∗, f∗) ∈ arg min g∈G,e∈E max f∈F EZ∼ν [f(g(Z), Z)]− Ex∼µ[f(X, e(X))],
where G, E ,F are referred to as the generator class, the encoder class, and the discriminator class, respectively. Suppose we have two independent random samples Z1, . . . , Zn
i.i.d.∼ ν and X1, . . . , Xn
i.i.d.∼ µ. At the sample level, the bidirectional GAN solves the empirical version of the above minimax problem:
(ĝθ, êϕ, f̂ω) = arg min gθ∈GNN ,eϕ∈ENN max fω∈FNN
1
n n∑ i=1 fω(gθ(Zi), Zi)− 1 n n∑ j=1 fω(Xj , eϕ(Xj)),
(2.1)
where GNN and ENN are two classes of neural networks approximating the generator class G and the encoder class E respectively, andFNN is a class of neural networks approximating the discriminator class F .

heading: 2.2 Assumptions
text: We assume the target µ and the reference ν satisfy the following assumptions. Assumption 1 (Subexponential tail). For a large n, the target distribution µ on Rd and the reference distribtuion ν on R satisfies the first moment tail condition for some δ > 0,
max{Eν‖Z‖1{‖Z‖>logn},Eµ‖X‖1{‖X‖>logn}} = O(n− (logn)δ d ).
Assumption 2 (Absolute continuity). Both the target distribution µ on Rd and the reference distribution ν on R are absolutely continuous with respect to the Lebesgue measure λ.
Assumption 1 is a technical condition for dealing with the case when µ and ν are supported on Rd and R instead of compact subsets. For distributions with bounded supports, this assumption is automatically satisfied. Here the factor (log n)δ ensures that the tails of µ and ν are sub-exponential, and it can be easily satisfied if the distributions are sub-gaussian. For the reference distribution, Assumption 1 and 2 can be easily satisfied by specifying ν as some common distribution with easyto-sample density such as Gaussian or uniform, which is usually done in the applications of GANs. For the target distribution, Assumption 1 and 2 specifies the type of distributions that are learnable by bidirectional GAN with our theoretical guarantees. Note that Assumption 1 is also necessary in our proof for bounding the generator and encoder approximation error in the sense that the results will not hold if we replace (log n)δ with 1. Assumption 2 is also necessary for Theorem 4.3 in mapping between empirical samples, which is essential in bounding generator and encoder approximation error.

heading: 2.3 Generator, encoder and discriminator classes
text: Let FNN := NN (W1, L1) be the discriminator class consisting of the feedforward ReLU neural networks fω : Rd+1 7→ R with width W1 and depth L1. Similarly, let GNN := NN (W2, L2) be the generator class consisting of the feedforward ReLU neural networks gθ : R 7→ Rd with width W2 and depth L2, and ENN := NN (W3, L3) the encoder class consisting of the feedforward ReLU neural networks eϕ : Rd 7→ R with width W3 and depth L3. The functions fω ∈ FNN have the following form:
fω(x) = AL1 · σ(AL1−1 · · ·σ(A1x+ b1) · · ·+ bL1−1) + bL1 where Ai are the weight matrices with number of rows and columns no larger than the width W1, bi are the bias vectors with compatible dimensions, and σ is the ReLU activation function σ(x) = x∨0. Similarly, functions gθ ∈ GNN and eϕ ∈ ENN have the following form:
gθ(x) = A ′ L2 · σ(A ′ L2−1 · · ·σ(A ′ 1x+ b ′ 1) · · ·+ b′L2−1) + b ′ L2 eϕ(x) = A ′′ L3 · σ(A ′′ L3−1 · · ·σ(A ′′ 1x+ b ′′ 1) · · ·+ b′′L3−1) + b ′′ L3
where A′i and A ′′ i are the weight matrices with number of rows and columns no larger than W2 and W3, respectively, and b′i and b ′′ i are the bias vectors with compatible dimensions.
We impose the following conditions on GNN , ENN , and FNN . Condition 1. For any gθ ∈ GNN and eϕ ∈ ENN , we have max{‖gθ‖∞, ‖eϕ‖∞} ≤ log n.
Condition 1 on GNN can be easily satisfied by adding an additional clipping layer ` after the original output layer, with cn,d ≡ (log n)/ √ d,
`(a) = a ∧ cn,d ∨ (−cn,d) = σ(a+ cn,d)− σ(a− cn,d)− cn,d. (2.2)
We truncate the output of ‖gθ‖ to an increasing interval [− log n, log n] to include the whole Rd support for the evaluation function class. Condition 1 on ENN can be satisfied in the same manner. This condition is technically necessary in our proof (see appendix).

heading: 3 Non-asymptotic error bounds
text: We characterize the bidirectional GAN solutions based on minimizing the integral probability metric (IPM, Müller (1997)) between two distributions µ and ν with respect to a symmetric evaluation function class F , defined by
dF (µ, ν) = sup f∈F
[Eµf − Eνf ]. (3.1)
By specifying the evaluation function class F differently, we can obtain many commonly-used metrics (Liu et al., 2017). Here we focus on the following two
• F = bounded Lipschitz function class : dF = dBL, (bounded Lipschitz (or Dudley) metric: metrizing weak convergence, Dudley (2018)), • F = Lipschitz function class : dF =W1 (Wasserstein GAN, Arjovsky et al. (2017)).
We consider the estimation error under the Dudley metric dBL. Note that in the case when µ and ν have bounded supports, the Dudley metric dBL is equivalent to the 1-Wasserstein metric W1. Therefore, under the bounded support condition for µ and ν, all our convergence results also hold under the Wasserstein distance W1. Even if the support of µ and ν are unbounded, we can still apply the result of Lu and Lu (2020) to avoid empirical process theory and obtain an stochastic error bound under the Wasserstein distance W1. However, the result of Lu and Lu (2020) requires sub-gaussianity to obtain the √ d prefactor. In order to make it more general, we use the empirical processes theory to get the explicit prefactor. Also, the discriminator approximation error will be unbounded if we consider the Wasserstein distance W1. Hence, we can only consider dBL for the unbounded support case.
The bidirectional GAN solution (ĝθ, êϕ) in (2.1) also minimizes the distance between (g̃θ)#ν̂n and (ẽϕ)#µ̂n under dFNN
min gθ∈GNN ,eϕ∈ENN dFNN ((g̃θ)#ν̂n, (ẽϕ)#µ̂n).
However, even if two distributions are close with respect to dFNN , there is no automatic guarantee that they will still be close under other metrics, for example, the Dudley or the Wasserstein distance (Arora et al., 2017). Therefore, it is natural to ask the question:
• How close are the two bidirectional GAN estimators ν̂ := (ĝθ, I)#ν and µ̂ := (I, êϕ)#µ under some other stronger metrics?
We consider the IPM with the uniformly bounded 1-Lipschitz function class on Rd+1, as the evaluation class, which is defined as, for some finite B > 0,
F1 := { f : Rd+1 7→ R ∣∣ |f(x)− f(y)| ≤ ‖x− y‖, x, y ∈ Rd+1 and ‖f‖∞ ≤ B} (3.2) In Theorem 3.1, we consider the bounded support case where dF =W1; In Theorem 3.2, we extend the result to the unbounded support case; In Theorem 3.3, we extend the result to the case where the dimension of the reference distribution is arbitrary.
We first present a result when µ is supported on a compact subset [−M,M ]d ⊂ Rd and ν is supported on [−M,M ] ⊂ R for a finite M > 0. Theorem 3.1. Suppose that the target µ is supported on [−M,M ]d ⊂ Rd and the reference ν is supported on [−M,M ] ⊂ R for a finite M > 0, and Assumption 2 holds. Let the outputs of gθ and eϕ be within [−M,M ]d and [−M,M ] for gθ ∈ GNN and eϕ ∈ ENN , respectively. By specifying the three network structures as W1L1 ≥ d √ ne, W 22L2 = C1dn, and W 23L3 = C2n for some constants 12 ≤ C1, C2 ≤ 384 and properly choosing parameters, we have
EdF1(ν̂, µ̂) ≤ C0 √ dn− 1 d+1 (log n) 1 d+1 ,
where C0 > 0 is a constant independent of d and n. The prefactor C0 √ d in the error bound depends on d1/2 linearly. This is different from the existing works where the dependence of the prefactor on d is either not clearly described or is exponential. In high-dimensional settings with large d, this makes a substantial difference in the quality of the error bounds. These remarks apply to all the results stated below.
The next theorem deals with the case of unbounded support. Theorem 3.2. Suppose Assumption 1 and 2 hold, and Condition 1 is satisfied. By specifying the structures of the three network classes as W1L1 ≥ d √ ne, W 22L2 = C1dn, and W 23L3 = C2n for some constants 12 ≤ C1, C2 ≤ 384 and properly choosing parameters, we have
EdF1(ν̂, µ̂) ≤ min { C0 √ dn− 1 d+1 (log n)1+ 1 d+1 , Cdn − 1d+1 log n } ,
where C0 is a constant independent of d and n, but Cd depends on d.
Note that two methods are used in bounding stochastic errors (see appendix), which leads to two different bounds: one with an explicit √ d prefactor with the cost that we have an additional log n factor. Another one with an implicit prefactor but with a better log n factor. Hence, it is a tradeoff between the explicitness of prefactor and the order of log n.
Our next result generalizes the results to the case when the reference distribution ν is supported on Rk for k ∈ N+.
Assumption 3. The target distribution µ on Rd is absolutely continuous with respect to the Lebesgue measure on Rd and the reference distribution ν on Rk is absolutely continuous with respect to the Lebesgue measure on Rk, and k d.
With the above assumption, we have the following theorem providing theoretical guarantees for the validity of any dimensional reference ν. Theorem 3.3. Suppose Assumption 1 and 3 hold, and Condition 1 is satisfied. By specifying generator and discriminator class structure as W1L1 ≥ d √ ne, W 22L2 = C1dn, and W 23L3 = C2kn for some constants 12 ≤ C1, C2 ≤ 384 and properly choosing parameters, we have
EdF1(ν̂, µ̂) ≤ min { C0 √ dn− 1 d+k (log n)1+ 1 d+k , Cdn − 1d+k log n } ,
where C0 is a constant independent of d and n, but Cd depends on d.
Note that the errors bounds established in Theorems 3.1-3.3 are tight up to a logarithmic factor, since the minimax rate measured in Wasserstein distance for learning distributions when the Lipschitz evaluation class is defined on Rd is Õ(n− 1d ) (Liang, 2020).

heading: 4 Approximation and stochastic errors
text: In this section we present a novel inequality for decomposing the total error into approximation and stochastic errors and establish bounds on these errors.

heading: 4.1 Decomposition of the estimation error
text: Define the approximation error of a function class F to another function classH by
E(H,F) := sup h∈H inf f∈F ‖h− f‖∞.
We decompose the Dudley distance dF1(ν̂, µ̂) between the latent joint distribution and the data joint distribution into four different error terms,
• the approximation error of the discriminator class FNN to F1:
E1 = E(F1,FNN ),
• the approximation error of the generator and encoder classes:
E2 = inf gθ∈GNN ,eϕ∈ENN sup fω∈FNN
1
n n∑ i=1 ( fω(gθ(zi), zi)− fω(xi, eϕ(xi)) ) ,
• the stochastic error for the latent joint distribution ν̂:
E3 = sup fω∈F1 Efω(ĝ(z), z)− Êfω(ĝ(z), z),
• the stochastic error for the latent joint distribution µ̂:
E4 = sup fω∈F1 Êfω(x, ê(x))− Efω(x, ê(x)).
Lemma 4.1. Let (ĝθ, êϕ) be the bidirectional GAN solution in (2.1) and F1 be the uniformly bounded 1-Lipschitz function class defined in (3.2). Then the Dudley distance between the latent joint distribution ν̂ = (ĝθ, I)#ν and the data joint distribution µ̂ = (I, êϕ)#µ can be decomposed as follows
dF1(ν̂, µ̂) ≤ 2E1 + E2 + E3 + E4. (4.1)
The novel decomposition (4.1) is fundamental to our error analysis. Based on (4.1), we bound each error term on the right side of (4.1) and balance the bounds to obtain an overall bound for the bidirectional GAN estimation.
For proving Lemma 4.1, we introduce the following useful inequality, which states that for any two probability distributions, the difference in IPMs with two distinct evaluation classes will not exceed 2 times the approximation error between the two evaluation classes, that is, for any probability distributions µ and ν and symmetric function classes F andH,
dH(µ, ν)− dF (µ, ν) ≤ 2E(H,F). (4.2)
It is easy to check that if we replace dH(µ, ν) by d̂H(µ, ν) := sup h∈H [Êµh− Êνh], (4.2) still holds.
Proof of Lemma 4.1. We have
dF1(ν̂, µ̂) = sup fω∈F1
Efω(ĝ(z), z)− Efω(x, ê(x))
≤ sup fω∈F1 Efω(ĝ(z), z)− Êfω(ĝ(z), z) + sup fω∈F1 Êfω(ĝ(z), z)− Êfω(x, ê(x))
+ sup fω∈F1
Êfω(x, ê(x))− Efω(x, ê(x))
=E3 + E4 + sup fω∈F1 Êfω(ĝ(z), z)− Êfω(x, ê(x)).
Denote A := supfω∈F1 Êfω(ĝ(z), z) − Êfω(x, ê(x)). By (4.2) and the optimality of the bidirectional GAN solutions, A satisfies
A = sup fω∈F1
1
n n∑ i=1 ( fω(ĝ(zi), zi)− fω(xi, ê(xi)) ) ≤ sup fω∈FNN 1 n n∑ i=1 ( fω(ĝ(zi), zi)− fω(xi, ê(xi)) ) + 2E(F1,FNN )
= inf gθ∈GNN ,eϕ∈ENN sup fω∈FNN
1
n n∑ i=1 ( fω(gθ(zi), zi)− fω(xi, eϕ(xi)) ) + 2E1
= 2E1 + E2.
Note that we cannot directly apply the symmetrization technic (see appendix) to E3 and E4 since e∗ and g∗ are correlated with xi and zi. However, this problem can be solved by replacing the samples (xi, zi) in the empirical terms in E3 and E4 with ghost samples (x′i, z′i) independent of (xi, zi) and replacing g∗ and e∗ with g∗∗ and e∗∗ which are obtained from the ghost samples, respectively. That is, we replace Êfω(g∗(z), z) and Êfω(x, e∗(x)) with Êfω(g∗∗(z′), z′) and Êfω(x′, e∗∗(x′)) in E3 and E4, respectively. Then we can proceed with the same proof of Lemma 4.1 and apply the symmetrization technic to E3 and E4, since (g∗(zi), zi) and (g∗∗(z′i), z′i) have the same distribution. To simplify the notation, we will just use Êfω(g∗(z), z) and Êfω(x, e∗(x)) to denote Êfω(g∗∗(z′), z′) and Êfω(x′, e∗∗(x′)) here, respectively.

heading: 4.2 Approximation errors
text: We now discuss the errors due to the discriminator approximation and the generator and encoder approximation.

heading: 4.2.1 The discriminator approximation error E1
text: The discriminator approximation error E1 describes how well the discriminator neural network class approximates functions from the Lipschitz class F1. Lemma 4.2 below can be applied to obtain the neural network approximation error for Lipschitz functions. It leads to a quantitative and nonasymptotic approximation rate in terms of the width and depth of the neural networks when bounding E1.
Lemma 4.2 (Shen et al. (2021)). Let f be a Lipschitz continuous function defined on [−R,R]d. For arbitrary W,L ∈ N+, there exists a function ψ implemented by a ReLU feedforward neural network with width W and depth L such that
||f − ψ||∞ = O (√ dR(WL)− 2 d ) .
By Lemma 4.2 and our choice of the architecture of discriminator class FNN in the theorems, we have E1 = O (√ d(W1L1) − 2d+1 log n ) . Theorem 4.2 also informs about how to choose the architecture of the discriminator networks based on how small we want the approximation error E1 to be. By setting (W1L1)2 ≥ n, E1 is dominated by the stochastic terms E3 and E4.

heading: 4.2.2 The generator and encoder approximation error E2
text: The generator and encoder approximation error E2 describes how powerful the generator and encoder classes are in pushing the empirical distributions µ̂n and ν̂n to each other. A natural question is
• Can we find some generator and encoder neural network functions such that E2 = 0?
Most of the current literature concerning the error analysis of GANs applied the optimal transport theory (Villani, 2008) to minimize an error term similar to E2, see, for example, Chen et al. (2020). However, the existence of the optimal transport function from R→ Rd is not guaranteed. Therefore, the existing analysis of GANs can only deal with the scenario when the reference and the target data distribution are assumed to have the same dimension. This equal dimensionality assumption is not satisfied in the actual training of GANs or bidirectional GANs in many applications. Here, instead of using the optimal transport theory, we establish the following approximation results in Theorem 4.3, which enables us to forgo the equal dimensionality assumption.
Theorem 4.3. Suppose that ν supported on R and µ supported on Rd are both absolutely continuous w.r.t. the Lebesgue measures, and z′is and x ′ is are i.i.d. samples from ν and µ, respectively for 1 ≤ i ≤ n. Then there exist generator and encoder neural network functions g : R 7→ Rd and e : Rd 7→ R such that g and e are inverse bijections of each other between {zi : 1 ≤ i ≤ n} and {xi : 1 ≤ i ≤ n} up to a permutation. Moreover, such neural network functions g and e can be obtained by properly specifying W 22L2 = c2dn and W 2 3L3 = c3n for some constant 12 ≤ c2, c3 ≤ 384.
Proof. By the absolute continuity of ν and µ, all the z′is and x ′ is are distinct a.s.. We can reorder z′is from the smallest to the largest, so z1 < z2 < . . . < zn. Let zi+1/2 be any point between zi and zi+1 for i ∈ {1, 2, . . . , n− 1}. We define the continuous piece-wise linear function g : R 7→ Rd by
g(z) =  x1 z ≤ z1, z−zi+1/2 zi−zi+1/2 xi + z−zi z i+1 2 −zixi+1 z = (zi, zi+1/2), for i = 1, . . . , n− 1,
xi+1 z ∈ [zi+1/2, zi+1], for i = 1, . . . , n− 2, xn z ≥ zn−1+1/2.
By Yang et al. (2021, Lemma 3.1) , g ∈ NN (W2, L2) if n ≤ (W2−d−1) ⌊ W2−d−1
6d ⌋⌊ L2 2 ⌋ . Taking
n = (W2 − d − 1) ⌊ W2−d−1
6d ⌋⌊ L2 2 ⌋ , a simple calculation shows W 22L2 = cdn for some constant
12 ≤ c ≤ 384. The existence of neural net function e can be constructed in the same way due to the fact that the first coordinate of x′is are distinct almost surely.
When the number of point masses of the empirical distributions are relatively moderate compared with the structure of the neural nets, we can approximate empirical distributions arbitrarily well with any empirical distribution with the same number of point masses pushforwarded by the neural nets.
Theorem 4.3 provides an effective way to specify the architecture of generator and encoder classes. According to this lemma, we can take n = W2−d2 ⌊ W2−d 6d ⌋⌊ L2 2 ⌋ + 2 = W3−12 ⌊ W3−1 6 ⌋⌊ L3 2 ⌋ + 2, which gives rise to W 22L2/d W 23L3 n. More importantly, Theorem 4.3 can be applied to
bound E2 as follows.
E2 = inf gθ∈GNN ,eϕ∈ENN sup fω∈FNN
1
n n∑ i=1 ( fω(gθ(zi), zi)− fω(xi, eϕ(xi)) ) ≤ inf gθ∈GNN sup fω∈FNN 1 n n∑ i=1 ( fω(gθ(zi), zi)− fω(xi, zi)
) + inf eϕ∈ENN sup fω∈FNN 1 n n∑ i=1 ( fω(xi, zi)− fω(xi, eϕ(xi))
) =0.
We simply reordered z′is and x ′ is as in the proof. Therefore, this error term can be perfectly eliminated.

heading: 4.3 Stochastic errors
text: The stochastic error E3 (E4) quantifies how close the empirical distribution and the true latent joint distribution (data joint distribution) are with the Lipschitz class F1 as the evaluation class under IPM. We apply the results in the refined Dudley inequality (Schreuder, 2020) in Lemma 4.4 to bound E3 and E4. Lemma 4.4 (Refined Dudley Inequality). For a symmetric function class F with supf∈F ||f ||∞ ≤ M , we have
E[dF (µ̂n, µ)] ≤ inf 0<δ<M
( 4δ +
12√ n ∫ M δ √ logN ( ,F , || · ||∞)d ) .
The original Dudley inequality (Dudley, 1967; Van der Vaart and Wellner, 1996) suffers from the problem that if the covering numberN ( ,F , || · ||∞) increases too fast as goes to 0, then the upper bound will be infinity, which is totally meaningless. The improved Dudley inequality circumvents such a problem by only allowing to integrate from δ > 0 as is shown in Lemma 4.4, which also indicates that EE3 scales with the covering number N ( ,F1, || · ||∞). By calculating the covering number of F1 and utilizing the refined Dudley inequality, we can obtain the upper bound
max{EE3,EE4} = O ( Cdn − 1d+1 log n ∧ √ dn− 1 d+1 (log n)1+ 1 d+1 ) . (4.3)

heading: 5 Related work
text: Recently, several impressive works have studied the challenging problem of the convergence properties of unidirectional GANs. Arora et al. (2017) noted that training of GANs may not have good generalization properties in the sense that even if training may appear successful but the trained distribution may be far from target distribution in standard metrics. On the other hand, Bai et al. (2019) showed that GANs can learn distributions in Wasserstein distance with polynomial sample complexity. Liang (2020) studied the rates of convergence of a class of GANs, including Wasserstein, Sobolev and MMD GANs. This work also established the nonparametric minimax optimal rate under the Sobolev IPM. The results of Bai et al. (2019) and Liang (2020) require invertible generator networks, meaning all the weight matrices need to be full-rank, and the activation function needs to be the invertible leaky ReLU activation. Chen et al. (2020) established an upper bound for the estimation error rate under Hölder evaluation and target density classes, where Hβ is Hölder class with regularity β and the density of the target µ is assumed to belong to Hα. They assumed that the reference distribution has the same dimension as the target distribution and applied the optimal transport theory to control the generator approximation error. However, how the prefactor depends in the error bounds on the dimension d in the existing results (Liang, 2020; Chen et al., 2020) is either not clearly described or is exponential. In high-dimensional settings with large d, this makes a substantial difference in the quality of the error bounds.
Singh et al. (2019) studied minimax convergence rates of nonparametric density estimation under a class of adversarial losses and investigated how the choice of loss and the assumed smoothness of the underlying density together determine the minimax rate; they also discussed connections to learning generative models in a minimax statistical sense. Uppal et al. (2019) generates the idea of Sobolev IPM to Besov IPM, where both target density and the evaluation classes are Besov classes. They also showed how their results imply bounds on the statistical error of a GAN.
These results provide important insights in the understanding of GANs. However, as we mentioned earlier, some of the assumptions made in these results, including equal dimension between the reference and target distributions and bounded support of the distributions, are not satisfied in the training of GANs in practice. Our results avoid these assumptions. Moreover, the prefactors in our error bounds are clearly described as being dependent on the square root of the dimension d. Finally, the aforementioned results only dealt with unidirectional GANs. Our work is the first to address the convergence properties of bidirectional GANs.

heading: 6 Conclusion
text: This paper derives the error bounds for the bidirectional GANs under the Dudley distance between the latent joint distribution and the data joint distribution. The results are established without the two crucial conditions that are commonly assumed in the existing literature: equal dimensionality between the reference and the target distributions and bounded support for these distributions. Additionally, this work contributes to the neural network approximation theory by constructing neural network functions such that the pushforward distribution of an empirical distribution can perfectly approximate another arbitrary empirical distribution with a different dimension as long as their number of point masses are equal. A novel decomposition of integral probability metric is also developed for error analysis of bidirectional GANs, which can be useful in other generative learning problems.
A limitation of our results, as well as all the existing results on the convergence properties of GANs, is that they suffer from the curse of dimensionality, which cannot be circumvented by assuming sufficient smoothness assumptions. In many applications, high-dimensional complex data such as images, texts and natural languages, tend to be supported on approximate lower-dimensional manifolds. It is desirable to take into such structure in the theoretical analysis. An important extension of the present results is to show that bidirectional GANs can circumvent the curse of dimensionality if the target distribution is assumed to be supported on an approximate lower-dimensional manifold. This appears to be a technically challenging problem and will be pursued in our future work.

heading: Acknowledgements
text: The authors wish to thank the three anonymous reviewers for their insightful comments and constructive suggestions that helped improve the paper significantly.
The work of J. Huang is partially supported by the U.S. NSF grant DMS-1916199. The work of Y. Jiao is supported in part by the National Science Foundation of China under Grant 11871474 and by the research fund of KLATASDSMOE. The work of Y. Wang is supported in part by the Hong Kong Research Grant Council grants 16308518 and 16317416 and HK Innovation Technology Fund ITS/044/18FX, as well as Guangdong-Hong Kong-Macao Joint Laboratory for Data-Driven Fluid Mechanics and Engineering Applications.

Review summaries:
The paper presents non-asymptotic error analysis for bidirectional GANs. The distinctive feature of the error analysis is relaxing the assumption that the data and latent variable should have the same dimension.  The constants in the error bound is also explicit in dimension.  

This paper studies the statistical properties of bidirectional GANs. It studies the sample complexity of the bidirectional GAN estimate under the Dudley metric. They relax a couple of assumptions usually made in GAN theory literature; they do not assume that the dimension of the latent distribution and the data distribution are the same or that the true data distribution has bounded support.