Year: 2021

Abstract:
Generative adversarial networks (GANs) are so complex that the existing learning theories do not provide a satisfactory explanation for why GANs have great success in practice. The same situation also remains largely open for deep neural networks. To fill this gap, we introduce a Lipschitz theory to analyze generalization. We demonstrate its simplicity by showing generalization and consistency of overparameterized neural networks. We then use this theory to derive Lipschitz-based generalization bounds for GANs. Our bounds show that penalizing the Lipschitz constant of the GAN loss can improve generalization. This result answers the long mystery of why the popular use of Lipschitz constraint for GANs often leads to great success, empirically without a solid theory. Finally but surprisingly, we show that, when using Dropout or spectral normalization, both truly deep neural networks and GANs can generalize well without the curse of dimensionality.

heading: 1 INTRODUCTION
text: In Generative Adversarial Networks (GANs) (Goodfellow et al., 2014), we want to train a discriminator D and a generator G by solving the following problem:
min G max D Ex∼Pd log(D(x)) + Ez∼Pz log(1−D(G(z))) (1)
where Pd is a data distribution that generates real data, and Pz is some noise distribution. G is a mapping that maps a noise z to a point in the data space. After training, G can be used to generate novel but realistic data.
Since its introduction (Goodfellow et al., 2014), a significant progress has been made for developing GANs and for interesting applications (Hong et al., 2019). Some recent works (Brock et al., 2019; Zhang et al., 2019; Karras et al., 2020b) can train a generator that produces synthetic images of extremely high quality. To explain those success, one popular way is to analyze generalization of the trained players. There are many existing theories (Mohri et al., 2018) for analyzing generalization. However, they suffer from various difficulties since the training problem of GANs is unsupervised in nature and contains two players competing against each other. Such a nature is entirely different from traditional learning problems. Neural distance (Arora et al., 2017) was introduced for analyzing generalization of GANs. One major limitation of existing distance-based bounds (Arora et al., 2017; Zhang et al., 2018; Jiang et al., 2019; Husain et al., 2019) is the strong dependence on the capacity of the family, which defines the distance between two distributions, sometimes leading to trivial bounds. This limitation prevents us from fullly understanding and identifying the key factors that contribute to the generalization of GANs. For example, it has long been theoretically unclear why Lipschitz constraint empirically can lead to great success in GANs?
The standard learning theories suffer from various difficulties when analyzing overparameterized neural networks (NNs). For example, Radermacher-based bounds (Bartlett & Mendelson, 2002; Golowich et al., 2020) can be trivial (Zhang et al., 2021); algorithmic stability (Shalev-Shwartz et al., 2010) and robustness (Xu & Mannor, 2012) may not be directly used since instability is the well-known issue when training GANs (Salimans et al., 2016; Arjovsky & Bottou, 2017; Xu et al., 2020). Those examples are among the reasons for why the theoretical study of modern deep learning is still in its infancy (Fang et al., 2021). Although some studies show generalization for shallow networks with at most one hidden layer (Arora et al., 2021; Mianjy & Arora, 2020; Mou et al., 2018; Kuzborskij & Szepesvári, 2021; Ji et al., 2021; Hu et al., 2021; Jacot et al., 2018), it has
long been theoretically unknown why deeper NNs can generalize better? Many great successes of deep learning often need huge datasets, but it has long been theoretically unknown whether or not the generalization of deep NNs suffers from the curse of dimensionality?
This work has the following contributions:
B We introduce a Lipschitz theory to analyze generalization of a learned function. This theory is surprizingly simple to analyze various complex models in general settings (including supervised, unsupervised, and adversarial settings).
BWe show that Dropout or spectrally-normalized neural networks avoid the curse of dimensionality. The number of layers required to ensure good generalization is logarithmic in sample size. It also suggests that deeper NNs can generalize better. We further show consistency and indentify a sufficient condition to guarantee high performance of DNNs. These results provide a significant step toward answering the open theoretical issues of deep learning (Zhang et al., 2021; Fang et al., 2021).
B Using Lipschitz theory, we provide a comprehensive analysis on generalization of GANs which resolves the two open challenges in the GAN community: (i) Our bounds apply to any particular D or G, and hence overcome the major limitation of existing works; In particular, for the first time in the literature, we show that Dropout and spectral normalization can help GANs to avoid the curse of dimensionality. (ii) Lipschitz constraint is used popularly through various ways including gradient penalty (Gulrajani et al., 2017), spectral normalization (Miyato et al., 2018), dropout, and data augmentation. Our analysis provides an unified explanation for why imposing a Lipschitz constraint can help GANs to generalize well in practice.
Organization: We will review related work in the next section. Section 3 presents the theory connecting Lipschitz continuity with generalization, and some analyses about deep neural networks. In Section 4, we analyze the generalization of GANs in various aspects. Section 5 concludes the paper.

heading: 2 RELATED WORK
text: Generalization in GANs: There are few efforts to analyze the generalization for GANs using the notion of neural distance, dD(Pd, Pg), which is the distance between two distributions (Pd, Pg), where D is the discriminator family.1 Arora et al. (2017) analyze generalization by bounding the quantity |dD(Pd, Pg) − dD(P̂d, P̂g)|, where (P̂d, P̂g) are empirical versions of (Pd, Pg). For a suitable choice of the loss V (Pd, Pz, D,G) in GANs, we can write |dD(Pd, Pg)−dD(P̂d, P̂g)| = |maxD∈D V (Pd, Pz, D,G)−maxD∈D V (P̂d, P̂z, D,G)|, where Pg is the induced distribution by putting samples from Pz through generatorG. Both Arora et al. (2017) and Husain et al. (2019) analyze |maxD∈D V (Pd, Pz, D,Go)−maxD∈D V (P̂d, P̂z, D,Go)| to see generalization of a trained Go, while (Zhang et al., 2018; Jiang et al., 2019) provide upper bounds for |maxD∈D V (Pd, P̂z, D,G) − minG∈G maxD∈D V (Pd, Pz, D,G)|. Note that those quantities of interest are non-standard in terms of learning theory.
A major limitation of those distance-based bounds (Arora et al., 2017; Zhang et al., 2018; Jiang et al., 2019; Husain et al., 2019) is the dependence on the notion of distance dD(·, ·) which relies on the best D ∈ D for measuring proximity between two distributions. The distance between two given distributions (µ, ν) may be small even when the two are far away (Arora et al., 2017). This is because there exists a perfect discriminator D, whenever µ and ν do not have overlapping supports (Arjovsky & Bottou, 2017). In those cases, a distance-based bound may be trivial. As a result, existing distance-based bounds are insufficient to understand generalization of GANs.
Qi (2020) shows a generalization bound for their proposed Loss-Sensitive GAN. Nonetheless, it is nontrivial to make their bound to work with other GAN losses. Wu et al. (2019) show that the discriminator will generalize if the learning algorithm is differentially private. Their concept of differential privacy basically requires that the learned function will change negligibly if the training set slightly changes. Such a requirement is known as algorithmic stability (Xu et al., 2010) and is nontrivial to assure in practice. Note that this assumption cannot be satisfied for GANs since their training is well-known to be unstable in practice.
1In general, D can be replaced by another family of functions to define the neural distance. However, for the ease of comparison with our work, the discriminator family is used.
Lipschitz continuity, stability, and generalization: Lipschitz continuity naturally appears in the formulation of Wasserstein GAN (WGAN) (Arjovsky et al., 2017). It was then quickly recognized as a key to improve various GANs (Fedus et al., 2018; Lucic et al., 2018; Mescheder et al., 2018; Kurach et al., 2019; Jenni & Favaro, 2019; Wu et al., 2019; Zhou et al., 2019; Qi, 2020; Chu et al., 2020). Gradient penalty (Gulrajani et al., 2017) and spectral normalization (Miyato et al., 2018) are two popular techniques to constraint the Lipschitz continuity ofD orGw.r.t their inputs. Some other works (Mescheder et al., 2017; Nagarajan & Kolter, 2017; Sanjabi et al., 2018; Nie & Patel, 2019) suggest to control the Lipschitz continuity of D or G w.r.t their parameters. Data augmentation is another way to control the Lipschitz constant of the loss, and is really beneficial for training GANs (Zhao et al., 2020a;b; Zhang et al., 2020; Tran et al., 2021). Those works empirically found that Lipschitz continuity can help improving stability and generalization of GANs. However, it has long been a mystery of why imposing a Lipschitz constraint can help GANs to generalize well. This work provides an unified explanation.

heading: 3 LIPSCHITZ CONTINUITY AND GENERALIZATION
text: In this section, we will present the main theory that connects Lipschitz continuity and generalization. We then discuss why deep neural networks can avoid the curse of dimensionality, and why deeper networks may generalize better.
Notations: Consider a learning problem specified by a function/hypothesis class H, an instance set X with diameter at most B, and a loss function f : H × X → R which is bounded by a constant C. Given a distribution Px defined on X , the quality of a function h(x) is measured by its expected loss F (Px, h) = Ex∼Px [f(h, x)]. Since Px is unknown, we need to rely on a finite training sample S = {x1, ..., xm} ⊂ X and often work with the empirical loss F (P̂x, h) = Ex∼P̂x [f(h, x)] = 1 m ∑ x∈S f(h, x), where P̂x is the empirical distribution defined on S. A learning algorithmA will pick a function hm ∈ H based on input S, i.e., hm = A(H,S). We first establish the following result whose proof appears in Appendix A. Theorem 1 (Lipschitz continuity ⇒ Generalization). If a loss f(h, x) is L-Lipschitz continuous w.r.t input x in a compact set X ⊂ Rnx , for any h ∈ H, and P̂x is the empirical distribution defined from m i.i.d. samples from distribution Px, then sup
h∈H |F (Px, h)− F (P̂x, h)| is upper-bounded by 1. Lλ + C √ (dBnxλ−nxe log 4− 2 log δ)/m with probability at least 1 − δ, for any constants δ ∈ (0, 1] and λ ∈ (0, B]. 2. (LB + 2C)m−α/nx with probability at least 1− 2 exp(−0.5mα), for any α ≤ nx/(2 + nx).
The assumption about Lipschitzness is natural. When learning a bounded function (e.g. a classifier), the assumption will satisfy if choosing a suitable loss (e.g. square loss, hinge loss, ramp loss, logistic loss, tangent loss, pinball loss) and H which has Lipschitz members with bounded ouputs. Crossentropy loss can satisfy if we require every h ∈ H to have outputs belonging to a closed interval in (0,1) or use label smoothing. Some recent works (Miyato et al., 2018; Gouk et al., 2021; Pauli et al., 2021) propose to put a penalty on the Lipschitz constant of h only. However, leaving open the Lipschitzness of f w.r.t h may not ensure a small Lipschitz constant of the loss.
This theorem tells that Lipschitz continuity is the key to ensure a function to generalize. Its generalization bounds can be better as the Lipschitz constant of the loss decreases. Note that there is a tradeoff between the Lipschitz constant and the expected loss F (Px, h) of the learnt function. A smaller L means that both f and h are getting simpler and flatter, and hence may increase F (Px, h). In contrast, a decrease of F (Px, h) may require h to be more complex and hence may increase L.
Theorem 1 presents generalization bounds, in a general setting, which suffer from the curse of dimensionality. This limitation is common for any other approaches without further assumptions (Bach, 2017). For some special classes, we can overcome this limitation as discussed next.

heading: 3.1 DEEP NEURAL NETWORKS THAT AVOID THE CURSE OF DIMENSIONALITY
text: We consider the two families of neural networks: one with bounded spectral norms for the weight matrices, and the other with Dropout. The following theorem whose proof appears in Appendix A.1 provides sharp bounds for the Lipschitz constant.
Theorem 2. Let fixed activation functions (σ1, . . . , σK), where σi is ρi-Lipschitz continuous. Let hW(x) := σK(WKσK−1(WK−1 . . . σ1(W1x) . . . )) be the neural network associated with weight matrices (W1, . . . ,WK), and Lh be the Lipschitz constant of h. Let the bounds (s1, . . . , sK) and (b1, . . . , bK) be given.
Spectrally-normalized networks (SN-DNN): Let Hsn = {hW : W = (W1, . . . ,WK), ‖Wi‖σ ≤ si}, where ‖ · ‖σ is the spectral norm. Then ∀h ∈ Hsn, Lh ≤ ∏K k=1 ρksk.
Dropout DNN: Let Hdr = {hW,q : hW,q = DrT (hW , q), ‖Wi‖F ≤ bi}, where DrT is the usual dropout training (Srivastava et al., 2014) with drop rate q for network hW , and ‖·‖F is the Frobenius norm. Then ∀h ∈ Hdr, Lh ≤ qK ∏K k=1 ρkbk.
Most popular activation functions (e.g., ReLU, Leaky ReLU, Tanh, SmoothReLU, Sigmoid, and Softmax) have small Lipschitz constants (ρk ≤ 1). This theorem suggests that the Lipschitz constant can be exponentially small as a neural network is deep (large K) and uses Dropout at each layer, since q < 1 is a popular choice in practice. On the other hand, the Lipschitz constant will be small if we control the spectral norms of weight matrices, e.g. by using spectral normalization. The Lipschitz constant will be exponentially smaller as the neural network is deeper and the spectral norm at each layer is smaller than 1. This case often happens as observed by Miyato et al. (2018).
The generalization of SN-DNNs and Dropout DNNs can be seen by combining Theorems 1 and 2. One can observe that, for the same norm bound on weight matrices, a network with smaller Lipschitz constant can provide a better bound. An interesting implication from Theorem 2 is that deeper networks (larger K) will have smaller Lipschitz constants and hence lead to better generalization bounds. This answers the second question of Section 1.
A trivial combination of Theorems 1 and 2 will result in a bound of O(m−1/nx) which suffers from the curse of dimensionality. The following theorem shows stronger results in Appendix A.1.
Theorem 3 (Generalization of DNNs). Given the assumptions in Theorems 1 and 2, let Lf be the Lipschitz constant of the loss f(h, x) w.r.t h, and δ ∈ (0, 1] be any given constant. 1. SN-DNNs: assume that there exist p ∈ (0, 1) and constant Csn such that CsnpK ≥ ∏K k=1 ρksk. If the number of layers K ≥ − 12 logpm, then the following holds with probability at least 1− δ: suph∈Hsn |F (Px, h)− F (P̂x, h)| ≤ ( CsnLfB + C √ log 4− 2 log δ ) m−0.5
2. Dropout DNNs: For Hdr with drop rate q ∈ (0, 1), let Cdr = ∏K k=1 ρkbk. If the number of layers K ≥ − 12 logqm, then the following holds with probability at least 1− δ: suph∈Hdr |F (Px, h)− F (P̂x, h)| ≤ ( CdrLfB + C √ log 4− 2 log δ ) m−0.5
The assumption of K ≥ − 12 logqm is naturally met in practice. For example, when training from 1.2M images, constant q = 0.5 requires K ≥ 10, and q = 0.1 requires K ≥ 3. Note that Alexnet (Krizhevsky et al., 2012) has 8 layers and the generator of StyleGAN (Karras et al., 2021) has 18 layers. The assumption about SN-DNNs can be satisfied when choosing activations with Lipschitz constant ρk < 1 or ensuring the spectral bound sk < 1 at any layer k. As mentioned before, such conditions are often satisfied in practice (Miyato et al., 2018) when using spectral normalization.
Comparison with state-of-the-art: Some recent studies (Bartlett et al., 2017; Neyshabur et al., 2018) provide generalization bounds for SN-DNNs for classification problems, using Radermacher complexity or PAC-Bayes. One major limitation of their works is that the sample size depends polynomially/exponentially on depth K. For SN-DNNs using ReLU, Golowich et al. (2020) improved the dependence to be linear in K if provided assumptions comparable with ours. In another view, when fixing m, their results require K = O(m) to get a meaningful generalization bound. This is impractical. In contrast, our result shows that it is sufficient to choose K which is logarithmic in m. Another limitation of the bounds in (Bartlett et al., 2017; Neyshabur et al., 2018; Golowich et al., 2020) is the dependence on 1/γ, where γ is the margin of the classification problem. Note that practical data may have a very small margin or may be inseparable. Hence those bounds are really limited and inapplicable to inseparable cases. On the contrary, Theorem 3 holds in general settings, including inseparable classification and unsupervised problems.
Our result for Dropout DNNs holds in general settings including unsupervised learning. This is significant since state-of-the-art studies about Dropout (Arora et al., 2021; Mianjy & Arora, 2020;
Mou et al., 2018) obtain efficient bounds only for networks with no more than 3 layers and for supervised learning. To the best of our knowledge, this work is the first showing that Dropout can help DNNs avoid the curse of dimensionality in general settings.

heading: 3.2 CONSISTENCY OF OVERPARAMETERIZED MODELS
text: We have discussed generalization of a function by bounding the difference between the empirical and expected losses. In some situations, those bounds may not be enough to explain a high performance, since both losses may be large despite their small difference. Next we consider consistency (ShalevShwartz et al., 2010) to see the goodness of a function compared with the best in its family. Definition 1. A learning algorithmA is said to be Consistent with rate cons(m) under distribution Px if for all m, ES∼Pmx |F (Px,A(H,S)) − F (Px, h
∗)| ≤ cons(m), where cons(m) must satisfy cons(m)→ 0 as m→∞, h∗ = argminh∈H F (Px, h).
Consistency says that, for any (but fixed) m, the learned function hm = A(H,S) is required to be (in expectation) close to the optimal h∗. The closeness is measured by |F (Px, hm) − F (Px, h∗)|. By considering this quantity, optimization error will naturally appear. We first show the following observation in Appendix A.2.
Lemma 1. Denote h∗ = argminh∈H F (Px, h) and P̂x is the empirical distribution defined from a sample S of size m. For any ho ∈ H, letting o = F (P̂x, ho)−minh∈H F (P̂x, h), we have: |F (Px, ho)− F (Px, h∗)| ≤ o + 2 suph∈H |F (Px, h)− F (P̂x, h)|
This lemma shows why the optimization error o and capacity of family H control the goodness of a function. Combining Theorem 1 with Lemma 1 will lead to the following. Theorem 4 (General family). Given the assumptions in Theorem 1, consider any function ho ∈ H. Let h∗ = argminh∈H F (Px, h), and o = F (P̂x, ho) − minh∈H F (P̂x, h) be the optimization error of ho on a sample S of size m. For any α ≤ nx/(2 + nx), with probability at least 1 − 2 exp(−0.5mα): |F (Px, ho)− F (Px, h∗)| ≤ o + 2(LB + 2C)m−α/nx . Corollary 1. Given the assumptions in Theorem 4, consider a learning algorithm A and family H. A is consistent if, for any given sample S of size m, the learned function ho = A(H,S) has optimization error at most o(m) which is a decreasing function of m, i.e., o(m)→ 0 as m→∞.
The assumption about optimization error o(m) is naturally satisfied when the training problem is convex. Indeed, it is well-known (Allen-Zhu, 2017; Schmidt et al., 2017) that gradient descent (GD) with T iterations can find a solution with error O(T−1) whereas stochastic gradient descent (SGD) with T iterations can find a solution with error O(T−0.5). Therefore, GD and SGD with T = O(m) iterations will satisfy this assumption. Note that convex training problems appear in many traditional models (Hastie et al., 2017), e.g., linear regression, support vector machines, kernel regression.
For DNNs, the training problems are often nonconvex and hence the assumption may not always hold. Surprisingly, overparameterized models can lead to tractable training problems. Indeed, (Allen-Zhu et al., 2019; Du et al., 2019; Zou et al., 2020; Nguyen & Mondelli, 2020; Nguyen, 2021) show that GD and SGD can find global solutions of the training problems for popular DNN families. For T iterations, GD and SGD can find a solution with error O(T−0.5). Those results suggests that T = O(m) iterations are sufficient to ensure our assumption about o(m). Allen-Zhu et al. (2019) show that T = O(logm) iterations are sufficient to ensure o(m) = O(m−1).
Combining Theorems 3 with Lemma 1 will lead to the following for Dropout DNNs. Similar results can be shown for SN-DNNs. Theorem 5 (Dropout family). Given the assumptions in Theorem 3, consider any ho ∈ Hdr. Let h∗ = argminh∈Hdr F (Px, h), and o = F (P̂x, ho) − minh∈Hdr F (P̂x, h) be the optimization error of ho on a sample S of size m. For any constant δ ∈ (0, 1], with probability at least 1 − δ: |F (Px, ho)− F (Px, h∗)| ≤ o + 2 ( CdrLfB + C √ log 4− 2 log δ ) m−0.5
Corollary 2 (Consistency of Dropout DNNs). Given the assumptions in Theorem 5, consider a learning algorithm A and family Hdr. If, for any given sample S of size m, the learned function ho = A(Hdr,S) has optimization error at most o(m) which is a decreasing function of m, then A is consistent with rate o(m) + 2 ( CdrLfB + C √ log 4− 2 log δ ) m−0.5.
Connection to overparameterization: Contrary to classical wisdoms about overfitting, modern machine learning exhibits a strange phenonmenon: very rich models such as neural networks are trained to exactly fit (i.e., interpolate and o = 0) the data, but often obtain high accuracy on test data (Belkin et al., 2019; Zhang et al., 2021). Those models often belong to overparameterization regime where the number of parameters in a model is far larger than m. Such a strikingly strange behavior could not be explained by traditional learning theories (Zhang et al., 2021). Some works try to understand overparameterization in linear regression (Bartlett et al., 2020) and kernel regression (Liang et al., 2020). Some recent results (Kuzborskij & Szepesvári, 2021; Ji et al., 2021; Hu et al., 2021; Jacot et al., 2018) on consistency hold only for shallow neural networks with no more than 3 layers. However, consistency of deep neural networks remains largely open.
For overparameterized NNs with a suitable width, T = O(m) iterations are sufficient for GD and SGD to achieve optimization error o(m) = O(m−0.5) as discussed before. Combining this observation with Corollary 2 will reveal consistency with rate O(m−0.5) for Dropout DNNs and SNDNNs. To the best of our knowledge, this is the first consistency result for overparameterized DNNs which are truly deep and avoid the curse of dimensionality.
Why are small consistency rates for high-capacity families sufficient to guarantee high generalization? To see why, consider GapB(ho, η) = F (Px, ho) − F (Px, η) which is the Bayes gap of an ho = A(H,S), where η denotes the (unknown) true function we are trying to learn. Note that GapB(ho, η) = Cons(ho,m) + F (Px, h∗) − F (Px, η), where Cons(ho,m) = F (Px, ho) − F (Px, h
∗) denotes the consistency rate. This decomposition suggests that a requirement of both Cons(ho,m) and F (Px, h∗) to be small will ensure a small GapB(ho, η), since F (Px, η) is independent ofH. In other words, a small consistency rate for high-capacityH is sufficient to guarantee high performance of ho on test data.
Overparameterized NNs often have a very high capacity. Some regularization methods can help us localize a subset Hg of the chosen NN family so that Hg has a small generalization gap. For example, in Theorem 3, we originally need to work with family H = {hW : ‖Wi‖F ≤ bi}, but Dropout localizes a subset Hdr ⊂ H having a small generalization gap. One should ensure that Hg still has a high capacity to produce a small optimization error. Interestingly, a small (even zero) optimization error is frequently observed in practice for overparameterized NNs (Zhang et al., 2021). In those cases, we can achieve a small consistency rate as shown in Corollary 2. Our work shows this property for Dropout and SN. Combining these arguments with the above sufficient condition will provide an answer for why those overparameterized NNs can work well on test data.

heading: 4 GENERALIZATION OF GANS
text: This section presents a comprehensive analysis on generalization of GANs. We then discuss why Lipschitz constraint succeeds in practice.
Notations: Let S = {x1, ..., xm, z1, ..., zm} consist of m i.i.d. samples from real distribution Pd defined on a compact set Zx ⊂ Rnx and m i.i.d. samples from noise distribution Pz defined on a compact setZz ⊂ Rn, P̂x and P̂z be the empirical distributions defined from S respectively. Denote D as the discriminator family and G as the generator family. Let v(D,G, x, z) = ψ1(D(x))+ψ2(1− D(G(z))) be the loss defined from a real example x ∼ Pd, a noise z ∼ Pz , a discriminator D ∈ D, and a generator G ∈ G. Different choices of the measuring functions (ψ1, ψ2) will lead to different GANs. For example, saturating GAN (Goodfellow et al., 2014) uses ψ1(x) = ψ2(x) = log(x); WGAN (Arjovsky et al., 2017) uses ψ1(x) = ψ2(x) = x; LSGAN (Mao et al., 2017; 2019) uses ψ1(x) = −(x+ a)2, ψ2(x) = −(x+ b)2 for some constants a, b; EBGAN (Zhao et al., 2017) uses ψ1(x) = x, ψ2(x) = max(0, r−x) for some constant r. We will often work with: V (Pd, Pz, D,G) = Ex∼Pdψ1(D(x))+Ez∼Pzψ2(1−D(G(z)));V (Pd, P̂z, D,G) = Ex∼Pdψ1(D(x))+Ez∼P̂zψ2(1−D(G(z))) V (P̂d, Pz, D,G) = Ex∼P̂dψ1(D(x)) + Ez∼Pzψ2(1 − D(G(z)));V (P̂d, P̂z, D,G) = Ex∼P̂dψ1(D(x)) + Ez∼P̂zψ2(1−D(G(z)))
In practice, we only have a finite sample S and an optimizer will solve minG∈G maxD∈D V (P̂d, P̂z, D,G) and return an approximate solution (Do, Go), which can be different from the training optimum (D∗o , G ∗ o) and Nash solution (D ∗, G∗), where
(D∗o , G ∗ o) = argmin
G∈G max D∈D
V (P̂d, P̂z, D,G), (D ∗, G∗) = argmin
G∈G max D∈D V (Pd, Pz, D,G) (2)
In learning theory, we often estimate (V (Pd, Pz, Do, Go) − V (P̂d, P̂z, Do, Go)) to see generalization. However a small bound on this quantity may not be enough, since V (Pd, Pz, Do, Go) can be far from the best V (Pd, Pz, D∗, G∗). Another way (Bousquet et al., 2004) is to see How good is (Do, Go) compared to the Nash solution (D∗, G∗)? In other words, we basically need to estimate the difference |V (Pd, Pz, Do, Go) − V (Pd, Pz, D∗, G∗)| = |V (Pd, Pz, Do, Go) − minG∈G maxD∈D V (Pd, Pz, D,G)| where V (Pd, Pz, Do, Go) shows the quality of the fake distribution induced by generator Go.
We first make the following error decomposition:
V (Pd, Pz, Do, Go)− V (Pd, Pz, D∗, G∗) = [V (Pd, Pz, Do, Go)− V (P̂d, P̂z, Do, Go)]+
[V (P̂d, P̂z, Do, Go)− V (P̂d, P̂z, D∗o , G∗o)] + [V (P̂d, P̂z, D∗o , G∗o)− V (Pd, Pz, D∗, G∗)] (3)
The first term (V (Pd, Pz, Do, Go) − V (P̂d, P̂z, Do, Go)) in the right-hand side of (3) shows the difference between the population and empirical losses of a specific solution (Do, Go). The second term (V (P̂d, P̂z, Do, Go) − V (P̂d, P̂z, D∗o , G∗o)) is in fact the Optimization error incurred by the optimizer. This error depends strongly on the capacity of the chosen optimizer. The third term (V (P̂d, P̂z, D∗o , G ∗ o)−V (Pd, Pz, D∗, G∗)) is optimizer-independent and strongly depends on the capacity of both families (D,G), since both V (P̂d, P̂z, D∗o , G∗o) and V (Pd, Pz, D∗, G∗) are optimizerindependent. We call this term Joint error of (D,G). In the next subsections, we will provide upper bounds on both the error of (Do, Go) and joint error of (D,G), and then generalization bounds that take the optimization error into account.
In the later discussions, we will often use the following assumptions and notation L = LψLdLg which upper bounds the Lipschitz constant of the loss v(D,G, x, z). Assumption 1. ψ1 and ψ2 are Lψ-Lipschitz continuous w.r.t. their inputs on a compact domain and upper-bounded by constant C ≥ 0. Assumption 2. Each generator G ∈ G is Lg-Lipschitz continuous w.r.t its input z over a compact set Zz ⊂ Rn with diameter at most Bz . Assumption 3. Each discriminator D ∈ D is Ld-Lipschitz continuous w.r.t its input x over a compact set Zx ⊂ Rnx with diameter at most Bx.
These assumptions are reasonable and satisfied by various GANs. For example, WGAN, LSGAN, EBGAN naturally satisfy Assumption 1, while saturating GAN will satisfy it if we constraint the output of D to be in [α, β] ⊂ (0, 1) as often used in practice. Spectral normalization and gradient penalty are popular techniques to regularize D and are crucial for large-scale generators (Zhang et al., 2019; Karras et al., 2020b). Therefore Assumptions 3 and 2 are natural.

heading: 4.1 ERROR BOUNDS
text: The following result readily comes from Theorem 1. Corollary 3. Given the assumptions (1, 2, 3), for any δ ∈ (0, 1], λ ∈ (0, Bz], with probability at least 1− δ, we have supD∈D,G∈G |V (Pd, Pz, D,G)− V (Pd, P̂z, D,G)| ≤ Lλ+ C√m √ dBnz λ−ne log 4− 2 log δ
This corollary tells the generalization of any generator G ∈ G, and can be further tighten by using Theorem 3 when using SN or Dropout. To see generalization of both players (Do, Go), observe that |V (Pd, Pz, Do, Go) − V (P̂d, P̂z, Do, Go)| ≤ supD∈D,G∈G |V (P̂d, P̂z, D,G) − V (Pd, Pz, D,G)|. The following theorem provides an upper bound whose proof appears in Appendix B.
Theorem 6. Denote (D,G) = supD∈D,G∈G |V (P̂d, P̂z, D,G) − V (Pd, Pz, D,G)|. Given the assumptions (1, 2, 3), for any constants δ, δx ∈ (0, 1], (General family) for any λ ∈ (0, Bz], λx ∈ (0, Bx], with probability at least 1− δ − δx: (D,G) ≤ Lλ+ C√
m √ dBnz λ−ne log 4− 2 log δ + LψLdλx + C√m √ dBnxx λ−nxx e log 4− 2 log δx
(D with spectral norm) given the assumptions in Theorem 3, with probability at least 1− 2δ: (Hsn,G) ≤ [CsnLψLgBz + 2C √ log 4− 2 log δ + CsnLψBx]m−0.5
(D with Dropout) given the assumptions in Theorem 3, with probability at least 1− 2δ: (Hdr,G) ≤ [CdrLψLgBz + 2C √ log 4− 2 log δ + CdrLψBx]m−0.5
For many models, such as WGAN, the measuring functions and D are Lipschitz continuous w.r.t their inputs. Note that the generator in WGAN, LSGAN, and EBGAN will be Lipschitz continuous w.r.t z, if we use some regularization methods such as gradient penalty or spectral normalization for both players. Theorem 6 also suggests that penalizing the zero-order (C) and first-order (L) informations of the loss can improve the generalization. This provides a significant evidence for the important role of gradient penalty or spectral normalization for the success of some large-scale generators (Zhang et al., 2019; Brock et al., 2019; Karras et al., 2020b).
It is worth observing that a small Lipschitz constant of the loss not only requires that both discriminator and generator are Lipschitz continuous w.r.t their inputs, but also requires Lipschitz continuity of the loss w.r.t both players. Most existing efforts focus on the players in GANs, and leave the loss open. Constraining on either D or G may be insufficient to ensure Lipschitz continuity of the loss.
One advantage of the generalization bounds in Theorem 6 is that the upper bounds on |V (P̂d, P̂z, D,G) − V (Pd, Pz, D,G)| hold true for any particular (D,G) in their families. Meanwhile, the existing generalization bounds (Arora et al., 2017; Zhang et al., 2018; Jiang et al., 2019; Wu et al., 2019; Husain et al., 2019) hold true conditioned on the best discriminator. Hence the bounds in Theorem 6 are more practical than existing ones, since D is not trained to optimality before training G in practical implementations of GANs.
Next we consider the joint error V (P̂d, P̂z, D∗o , G ∗ o) − V (Pd, Pz, D∗, G∗) of both families (D,G). Such a quantity also shows the goodness of the training optimum (D∗o , G ∗ o) compared with the Nash solution (D∗, G∗). It is worth observing that |V (P̂d, P̂z, D∗o , G∗o) − V (Pd, Pz, D∗, G∗)| = |minG∈G maxD∈D V (P̂d, P̂z, D,G)−minG∈G maxD∈D V (Pd, Pz, D,G)|measures the quality of the best players given a finite number of samples only, and such error does not depend on any optimizer. Hence it represents the Joint capacity of both generator and discriminator families. The following theorem provides an upper bound whose proof appears in Appendix B. Theorem 7. Given the assumptions (1, 2, 3), for any constants δ, δx ∈ (0, 1], λ ∈ (0, Bz], λx ∈ (0, Bx], with probability at least 1 − δ − δx: |V (P̂d, P̂z, D∗o , G∗o) − V (Pd, Pz, D∗, G∗)| ≤ Lλ + C√ m √ dBnz λ−ne log 4− 2 log δ + LψLdλx + C√m √ dBnxx λ−nxx e log 4− 2 log δx.
This bound on joint capacity of (D,G) is loose, since few informations about those families are used. We can tighten this bound when using SN or Dropout for D, similar with Theorem 6.

heading: 4.2 FROM OPTIMIZATION ERROR TO GENERALIZATION
text: Finally we make a bidge between optimization error and generalization. The decomposition (3) contains three components, for which the first component is bounded in Theorem 6 while the third component is bounded in Theorem 7. Combining those observations will lead to the following result. Theorem 8 (Generalization bounds for GANs). Assume the assumptions (1, 2, 3) and the optimization error |V (P̂d, P̂z, Do, Go) − min
G∈G max D∈D V (P̂d, P̂z, D,G)| ≤ o. Denote cons(D,G) = |V (Pd, Pz, Do, Go)− V (Pd, Pz, D∗, G∗)|. For any constants δ, δx ∈ (0, 1],
1. (General family) for any λ ∈ (0, Bz], λx ∈ (0, Bx], with probability at least 1− δ − δx: cons(D,G) ≤ o + 2Lλ + 2C√m √ dBnz λ−ne log 4− 2 log δ + 2LψLdλx +
2C√ m
√ dBnxx λ−nxx e log 4− 2 log δx.
2. (Spectral norm) given the assumptions in Theorem 3, D ≡ Hsn, with probability at least 1− 2δ: cons(Hsn,G) ≤ o + 2[CsnLψLgBz + 2C √ log 4− 2 log δ + CsnLψBx]m−0.5
3. (Dropout) given the assumptions in Theorem 3, D ≡ Hdr, with probability at least 1− 2δ: cons(Hdr,G) ≤ o + 2[CdrLψLgBz + 2C √ log 4− 2 log δ + CdrLψBx]m−0.5
Theorems 6 and 8 provide us a comprehensive view about generalization of GANs. Note that their assumptions are naturally met in practice as pointed out before. For the first time in the GAN litera-
ture, our work reveals that GANs can avoid the curse of dimensionality when choosing appropriate (D,G). Furthermore, a logarithmic (in m) number of layers are sufficient for each player. Although this work shows this property for DNNs with spectral norm or Dropout. We believe that this property can hold for many other DNN families.
One important implication from Theorem 8 is that GANs can be consistent under suitable conditions. An example condition is overparameterization, for which the optimization error can be zero. Our experiments in Appendix F provide a good evidence for this conjecture as the well-trained discriminators often reach Nash equilibria. A recent investigation about optimization of overparameterized GANs appears in (Balaji et al., 2021). We leave this door open for the readers.

heading: 4.3 WHY A LIPSCHITZ CONSTRAINT IS CRUCIAL
text: Various works (Guo et al., 2019; Jenni & Favaro, 2019; Qi, 2020; Arjovsky et al., 2017; Gulrajani et al., 2017; Roth et al., 2017; Miyato et al., 2018; Zhou et al., 2019; Thanh-Tung et al., 2019; Jiang et al., 2019; Tanielian et al., 2020; Xu et al., 2020) try to ensure Lipschitz continuity of the discriminator or generator. The most popular techniques are gradient penalty (Gulrajani et al., 2017) and spectral normalization (SN) (Miyato et al., 2018). Those techniques are really useful for different losses (Fedus et al., 2018) and high-capacity architectures (Kurach et al., 2019). From a large-scale evaluation, Kurach et al. (2019) found that gradient penalty can help the performance of GANs but does not stabilize the training, whereas using SN for G only is insufficient to ensure stability (Brock et al., 2019). Some recent large-scale generators (Brock et al., 2019; Zhang et al., 2019; Karras et al., 2020b) use gradient penalty or SN to ensure their successes. Data augmentation (Zhao et al., 2020a;b; Tran et al., 2021; Karras et al., 2020a) also contributes to the excellent performance of GANs in practice, due to implicitly penalizing the Lipschitz constant of the loss (see Appendix D for explanation). Those empirical observations without a theory poses a long mystery of why can imposing a Lipschitz constraint help GANs to perform well? This work provides an answer:
. Theorems 6 and 8 show that a Lipschitz constraint on one player (D or G) can help, but may be not enough. A penalty on the first-order (L) information of the loss can lead to better generalization.
. Spectral normalization (Miyato et al., 2018) is a popular technique to regularize GANs. Using SN, the spectral norms of the weight matrices are often small in practice, and hence the Lipschitz constant of D (or G) can be exponentially small when using SN. In those cases, the assumptions of Theorem 8 are satisfied. Therefore the generalization bound in Theorem 8 is tight and supports well the success of spectrally-normalized GANs (Miyato et al., 2018; Zhang et al., 2019).
. Dropout and SN are really efficient to control the complexity of the players and provide tight generalization bounds.
.WGAN (Arjovsky et al., 2017) naturally requiresD to be 1-Lipschitz continuous. Weight clipping is used so that every element of network weights belongs to [−c, c] for some constant c. For some choices, e.g. c = 0.01 in (Arjovsky et al., 2017), the spectral norm of the weight matrix at each layer can be smaller than 1.2 In those cases the Lipschitz constant of D can be exponentially small, leading to tight bounds in Theorem 8 and better generalization.
. SN, gradient penalty, and data augmentation are crucial parts of large-scale GANs (Brock et al., 2019; Zhang et al., 2019; Karras et al., 2020b). As a result, Theorems 6 and 8 provide a strong support for their success in practice.
. Our experiments with SN in Appendix F indeed show that SN can reduce the Lipschitz constants of the players and the loss. However, when SN is overused, the trained players can get underfitting and may hurt generalization. A reason is that an underfitted model can have a bad population loss and high optimization error.

heading: 5 CONCLUSION
text: We have presented a simple way to analyze generalization of various complex models that are hard for traditional learning theories. Some successful applications were done and made a significant step toward understanding DNNs and GANs. One limitation of our bounds is that the optimization aspect is left open.
2For c = 0.01, if the number of units at each layer is no more than 100, then the Frobenius norm of the weight matrice at each layer is smaller than 1, and so is for the spectral norm.

heading: A LIPSCHITZ CONTINUITY⇒ GENERALIZATION
text: This section provides the proofs for the theorems of Section 3. Let X = ⋃N i=1 Xi be a partition of X into N disjoint subsets. We use the following definition from Xu & Mannor (2012).
Definition 2 (Robustness). An algorithmA is (N, )-robust, for : Xm → R, if the following holds for all S ∈ Xm: ∀s ∈ S,∀x ∈ X ,∀i ∈ {1, ..., N}, if s, x ∈ Xi then |f(A(H,S), s)− f(A(H,S), x)| ≤ (S).
Basically, a robust algorithm will learn a hypothesis which ensures that the losses of two similar data instances should be the same. A small change in the input leads to a small change in the loss of the learnt hypothesis. In other words, the robustness ensures that each testing sample which is close to the training dataset will have a similar loss with that of the closest training samples. Therefore, the hypothesis A(H,S) will generalize well over the areas around S.
Theorem 9 (Xu & Mannor (2012)). If a learning algorithmA is (N, )-robust and the training data S is an i.i.d. sample from distribution Px, then for any δ ∈ (0, 1] we have the following with probability at least 1− δ: |F (Px,A(H,S))− F (P̂x,A(H,S))| ≤ (S) + C √ (N log 4− 2 log δ)/m.
This theorem formally makes the important connection between robustness of an algorithm and generalization. If an algorithm is robust, then its resulting hypotheses can generalize. One important implication of this result is that we should ensure the robustness of a learning algorithm. However, it is nontrivial to do so in general.
Let us have a closer look at robustness. (S) in fact bounds the amount of change in the loss with respect to a change in the input given a fixed hypothesis. This observation suggests that robustness closely resembles the concept of Lipschitz continuity. Remember that a function y : X → Y is said to be L-Lipschitz continuous if dy(y(x), y(x′)) ≤ Ldx(x, x′) for any x, x′ ∈ X , where dx is a metric on X , dy is a metric on Y, and L ≥ 0 is the Lipschitz constant. Therefore, we establish the following connection between robustness and Lipschitz continuity.
Lemma 2. Given any constant λ > 0, consider a loss f : H × X → R, where X ⊂ Rnx is compact, B = diam(X ) = maxx,x′∈X ||x− x′||∞, N = dBnxλ−nxe. If for any h ∈ H, f(h, x) is L-Lipschitz continuous w.r.t input x, then any algorithm A that maps Xm toH is (N,Lλ)-robust.
Proof: It is easy to see that there exist N = d(B/λ)nxe disjoint nx-dimensional cubes, each with edge length of λ, satisfying that their union covers X completely since X is compact. Let Ck be one of those cubes, indexed by k, and Xk = X ∩ Ck. We can write X = ⋃N k=1 Xk. Consider any s, x ∈ X . If both s and x belong to the same Xk for some k, then we have∣∣f(A(H,S), s)− f(A(H,S), x)∣∣ ≤ L||s − x||∞ ≤ Lλ for any algorithm A and any S ∈ Xm due to the Lipschitz continuity of f , completing the proof.
Proof of Theorem 1: For any h ∈ H and dataset S, there exists an algorithm A that maps S to h, i.e., h = A(H,S). Lemma 2 tells thatA is (dBnxλ−nxe, Lλ)-robust for any λ ∈ (0, B]. Theorem 9 implies |F (Px, h) − F (P̂x, h)| ≤ Lλ + C√m √ dBnxλ−nxe log 4− 2 log δ with probability at least 1 − δ, for any constants δ ∈ (0, 1] and λ ∈ (0, B]. Since this bound holds true for any h ∈ H, we conclude
sup h∈H |F (Px, h)− F (P̂x, h)| ≤ Lλ+ C√ m
√ dBnxλ−nxe log 4− 2 log δ
The second statement is an application of the first one by taking λ = Bm−α/nx and δ = 2 exp(−0.5mα). Indeed,
sup h∈H |F (Px, h)− F (P̂x, h)| ≤ Lλ+ C√ m
√ dBnxλ−nxe log 4− 2 log δ
≤ LBm− α nx + C√ m
√ dmαe log 4− log 4 +mα
≤ LBm− α nx + C√ m
√ mα log 4 +mα
≤ LBm− α nx + Cm− α nx √ (1 + log 4)m−1+ nx+2 nx α
≤ (LB + 2C)m− α nx
The last inequality holds because −1 + nx+2nx α ≤ 0 and hence m −1+nx+2nx α ≤ 1, completing the proof.

heading: A.1 DEEP NEURAL NETWORKS THAT AVOID THE CURSE OF DIMENSIONALITY
text: Proof of Theorem 2: Denote h0(x) = x, h1(x) = σ1(W1h0(x)), ..., hK(x) = σK(WKhK−1(x)). By definition, the Lipschitz constant of a function g(h) is defined to be ‖g‖Lip = sup
‖h‖2≤1 σ(∇g(h)),
where σ(B) is the spectral norm of matrix B. For a linear function we have ‖Wh‖Lip = sup ‖h‖2≤1 σ(Wh) = ‖W‖σ . Since σi is ρi-Lipschitz for any i, we have
‖hK(x)‖Lip ≤ ρK‖WKhK−1(x)‖Lip (4) ≤ ρK‖WK‖σ‖hK−1(x)‖Lip (5) ≤ ρKρK−1‖WK‖σ‖WK−1‖σ‖hK−2(x)‖Lip (6) ... (7)
≤ K∏ k=1 ρk‖Wk‖σ (8)
≤ K∏ k=1 ρksk (9)
which proves the first statement.
Next consider a neural network hA trained with Dropout (Srivastava et al., 2014). At each minibatch t of the training phase, we randomly sample a thin sub-network of hW , compute the gradients g(t)(x) given the minibatch data, and then update each weight matrice as
W (t) i := Normalize(Ŵ (t) i )c where Ŵ (t) i :=W (t−1) i − ηg (t) i (x) (10)
whereNormalize(Ŵ (t)i )c is the normalization so that ‖W (t) i ‖F ≤ ci ≤ bi for some tuning constant ci and any i, and η is the learning rate.
After training (with T minibatchs), the network weights are scaled as W (T )i := qW (T ) i for any i, where q is the drop rate. This implies that after training, we obtain a neural network hW,q with all weight matrices satisfying ‖Wi‖F ≤ qbi. By using the same arguments as above, we have
‖hW,q(x)‖Lip ≤ K∏ k=1 ρk‖Wk‖σ (11)
≤ K∏ k=1 ρk‖Wk‖F (12)
≤ K∏ k=1 ρkqbk (13)
where we have used the fact that ‖B‖σ ≤ ‖B‖F for any B, completing the proof.
Proof of Theorem 3: Let L be the Lipschitz constant of loss f(h, x) w.r.t x. The basic property of Lipschitz functions and composition shows that L ≤ LfLh. For any h ∈ Hdr, we have Lh ≤ qKCdr owing to Theorem 2. Hence L ≤ LfqKCdr ≤ LfCdrm−0.5. Taking λ = B, Theorem 1 tells that
sup h∈Hdr
|F (Px, h)−F (P̂x, h)| ≤ LB+C √ (log 4− 2 log δ)/m ≤ BLfCdrm−0.5+C √ (log 4− 2 log δ)/m
Similar arguments can be used for familyHsn, completing the proof.

heading: A.2 CONSISTENCY PROOF
text: Proof of Lemma 1: We have
|F (Px, ho)− F (Px, h∗)|
= |F (Px, ho)− F (P̂x, ho) + F (P̂x, ho)−min h∈H F (P̂x, h) + min h∈H F (P̂x, h)−min h∈H F (Px, h)|
≤ |F (Px, ho)− F (P̂x, ho)|+ |F (P̂x, ho)−min h∈H F (P̂x, h)|+ |min h∈H F (P̂x, h)−min h∈H F (Px, h)|(14)
≤ |F (Px, ho)− F (P̂x, ho)|+ o + sup h∈H |F (P̂x, h)− F (Px, h)| (15)
≤ o + 2 sup h∈H |F (P̂x, h)− F (Px, h)|
where we have used Lemma 3 to derive (15) from (14).

heading: B PROOFS OF THE MAIN THEOREMS FOR GANS
text: Proof of Corollary 3: Observe that sup
D∈D,G∈G |V (Pd, Pz, D,G) − V (Pd, P̂z, D,G)| = sup D∈D,G∈G |Ez∼Pzψ2(1 − D(G(z))) −
Ez∼P̂zψ2(1−D(G(z)))|. Since P̂z is an empirical version of Pz , applying Theorem 1 will provide the generalization bounds for supD∈D,G∈G |Ez∼Pzψ2(1−D(G(z)))− Ez∼P̂zψ2(1−D(G(z)))|.
The same arguments can be done for supD∈D,G∈G |V (P̂d, Pz, D,G)− V (P̂d, P̂z, D,G)|, completing the proof.
Proof of Theorem 6: Observe that |V (P̂d, P̂z, D,G)− V (Pd, Pz, D,G)|
= ∣∣∣Ex∼P̂dψ1(D(x)) + Ez∼P̂zψ2(1−D(G(z)))− Ex∼Pd,z∼Pzv(D,G, x, z)∣∣∣ (16)
≤ |Ez∼Pzψ2(1−D(G(z)))− Ez∼P̂zψ2(1−D(G(z)))|+ |Ex∼Pdψ1(D(x))− Ex∼P̂dψ1(D(x))|
Therefore supG∈G,D∈D |V (P̂d, P̂z, D,G)− V (Pd, Pz, D,G)|
≤ sup G∈G,D∈D |Ez∼Pzψ2(1−D(G(z)))− Ez∼P̂zψ2(1−D(G(z)))|
+ sup G∈G,D∈D |Ex∼Pdψ1(D(x))− Ex∼P̂dψ1(D(x))| (17)
Theorem 1 shows that sup G∈G,D∈D |Ez∼Pzψ2(1 − D(G(z))) − Ez∼P̂zψ2(1 − D(G(z)))| ≤ Lλ + C √
(dBnz λ−ne log 4− 2 log δ)/m, with probability at least 1 − δ, for any constants δ ∈ (0, 1] and λ ∈ (0, Bz]. Similarly, we have sup
G∈G,D∈D |Ex∼Pdψ1(D(x)) − Ex∼P̂dψ1(D(x))| ≤ LψLdλx + C √
(dBnxx λ−nxx e log 4− 2 log δx)/m, with probability at least 1− δx, for any constants δx ∈ (0, 1] and λx ∈ (0, Bx]. Combining these bounds with (17) and the union bound will lead to the first statement of the theorem.
For the second and third statements, we choose λ = Bz, λx = Bx, δ = δx. Using the bounds for the Lipschitz constant of D in Theorem 3 will complete the proof.
Proof of Theorem 7: By definition, (D∗o , G∗o) = argminG∈G maxD∈D V (P̂d, P̂z, D,G) and (D∗, G∗) = argminG∈G maxD∈D V (Pd, Pz, D,G).
Therefore |V (P̂d, P̂z, D∗o , G∗o)− V (Pd, Pz, D∗, G∗)| = |min
G∈G max D∈D V (P̂d, P̂z, D,G)−min G∈G max D∈D V (Pd, Pz, D,G)| (18)
≤ max G∈G |max D∈D V (P̂d, P̂z, D,G)−max D∈D V (Pd, Pz, D,G)| (19)
≤ max G∈G max D∈D |V (P̂d, P̂z, D,G)− V (Pd, Pz, D,G)| (20)
≤ Lλ+ C √ (dBnz λ−ne log 4− 2 log δ)/m+ LψLdλx + C √ (dBnxx λ−nxx e log 4− 2 log δx)/m(21)
where we have used Lemma 3 to derive (20) from (19) and (21) from (20). The last inequality comes from Theorem 6, completing the proof.
Lemma 3. Assume that h1 and h2 are continuous functions defined on a compact set Zx. Then |max x∈Zx h1(x)− max x∈Zx h2(x)| ≤ max x∈Zx |h1(x)− h2(x)|
| min x∈Zx h1(x)− min x∈Zx h2(x)| ≤ max x∈Zx |h1(x)− h2(x)|
Proof: Denote x∗1 = argmaxx∈Zx h1(x), x ∗ 2 = argmaxx∈Zx h2(x). It is easy to see that
h1(x ∗ 2)− h2(x∗2) ≤ h1(x∗1)− h2(x∗2) ≤ h1(x∗1)− h2(x∗1)
Therefore |max x∈Zx h1(x)− max x∈Zx h2(x)| = |h1(x∗1)− h2(x∗2)| ≤ max x∈Zx |h1(x)− h2(x)|.
We can rewrite |minx∈Zx h1(x) − minx∈Zx h2(x)| = | − maxx∈Zx(−h1(x)) + maxx∈Zx(−h2(x))| ≤ maxx∈Zx |h1(x)− h2(x)|, completing the proof.

heading: C GANS AND AUTOENCODERS

heading: C.1 TIGHTNESS OF THE BOUNDS FOR GANS
text: Note that our bounds in Theorems 6 and 8 in general are not tight in terms of sample complexity and dimensionality. Taking λ = Bzm−1/(n+2), δ = 2 exp(−0.5mn/(n+2)), λx = Bxm−1/(nx+2), δx = 2 exp(−0.5mnx/(nx+2)), Theorem 6 provides supD∈D,G∈G |V (P̂d, P̂z, D,G) − V (Pd, Pz, D,G)| ≤ O(m−1/(n+2) +m−1/(nx+2)). This bound O(m−1/(n+2) +m−1/(nx+2)) surpasses the previous best bound O(m−1/(1.5n) +m−1/(1.5nx)) in the GAN literature (Husain et al., 2019).

heading: C.2 SAMPLE-EFFICIENT BOUNDS FOR AUTOENCODERS
text: Husain et al. (2019) did a great job at connecting GANs and Autoencoder models. They showed that the generator objective in f -GAN (Nowozin et al., 2016) is upper bounded by the objective of Wasserstein Autoencoders (WAE) (Tolstikhin et al., 2018). Under some suitable conditions, the two objectives equal. They further showed the bound:
|max D∈D V (Pd, Pz, D,G)−max D∈D V (P̂d, P̂z, D,G)| ≤ O(m−1/sd +m−1/sg ),
where sd > d∗(Pd) (the 1-upper Wasserstein dimension of Pd) and sg > d∗(Pg). We show in Appendix C.3 that sd > 1.5nx, sg > 1.5n even for a simple distribution, where nx is the dimensionality of real data, and n is the dimensionality of latent codes. Therefore their bound becomes O(m− 1 1.5nx +m− 1 1.5n ), which is significantly worse than our bound O(m−1/(n+2)+m−1/(nx+2)). As a result, our work provides tighter generalization bounds for both GANs and Autoencoder models. More importantly, our results for DNNs with Dropout or spectral norm translate directly to Autoencoders, leading to significant tighter bounds.

heading: C.3 HOW LARGE IS 1-UPPER WASSERSTEIN DIMENSION?
text: This part provides an example of why 1-upper Wasserstein dimension is not small. Before that we need to take the following definitions from Husain et al. (2019).
Definition 3 (Covering number). For a set S ⊂ Rn, we denote Nη(S) be the η-covering number of S, which is the smallest non-negative integer m such that there exists closed balls B1, B2, ..., Bm of radius η with S ⊆ ⋃m i=1Bi. For any distribution P , the (η, τ)-dimension is dη(P, τ) := logNη(P,τ) − log η , where Nη(P, τ) := inf{Nη(S) : P (S) ≥ 1− τ}. Definition 4 (1-upper Wasserstein dimension). The 1-upper Wasserstein dimension of distribution P is
d∗(P ) := inf{s ∈ (2,∞) : lim sup η→0 dη(P, η s s−2 ) ≤ s}
Consider the simple case of the unit Gaussian distribution P ≡ N (x; 0, I) defined in the ndimensional space Rn. We will show that the 1-upper Wasserstein dimension of P is d∗(P ) ≥ 1.5n.
First of all, we need to see the region S such that P (S) ≥ 1 − η s s−2 . Since P is a Gaussian, the Birnbaum-Raymond-Zuckerman inequality tells that Pr(||x||22 ≥ nη− s s−2 ) ≤ η s s−2 . It implies that Pr(||x||22 ≤ nη− s s−2 ) ≥ 1− η s s−2 . In other words, S is the following ball:
S = {x ∈ Rn : ||x||22 ≤ nη− s s−2 }
As a consequence, we can lower bound the covering number of S as
Nη(S) ≥  √ nη− s s−2
η
 n = ( nη −3s+4 s−2 )n 2
By definition we have
Nη(P, η s s−2 ) = inf{Nη(S) : P (S) ≥ 1− η s s−2 } ≥ ( nη −3s+4 s−2 )n 2
Next we observe that
dη(P, η s s−2 ) =
1
− log η logNη(P, η
s s−2 ) (22)
≥ 1 − log η
[ n
2 log n+
n
2 ( −3s+ 4 s− 2 ) log η ] (23)
≥ n 2 ( 3s− 4 s− 2 ) − n 2 log η log n (24)
Therefore
lim sup η→0
dη(P, η s s−2 ) ≥ n
2 ( 3s− 4 s− 2 ) (25)
The definition of d∗(P ) requires lim supη→0 dη(P, η s s−2 ) ≤ s and s ∈ (2,∞). Those requirements imply n2 ( 3s−4 s−2 ) ≤ s, and thus s ≥ 14 ( 4 + 3n+ √ (4 + 3n)2 − 32n ) > 3n2 . As a result, d ∗(P ) > 1.5n.

heading: D WHY DOES DATA AUGMENTATION IMPOSE A LIPSCHITZ CONSTRAINT?
text: In this section, we study a perturbed version of GANs to see the implicit role of data augmentation (DA). Consider the following formulation:
min G max D Ex∼PdE [logD(x+ )] + Ez∼PzE [log(1−D(G(z) + ))] (26)
where = σu and u follows a distribution with mean 0 and covariance matrix I , σ is a non-negative constant. Note that when u is the Gaussian noise, the formulation (26) turns out to be the noisy version of GAN (Arjovsky & Bottou, 2017).
Noise penalizes the Jacobian norms: Adding noises to the discriminator inputs corresponds to making a convolution to real and fake distributions (Roth et al., 2017; Arjovsky & Bottou, 2017). Let pd∗ (x) = E [pd(x+ )], pg∗ (x) = E [pg(x+ )] be the density functions of the convoluted distributions Pd∗ , Pg∗ , respectively. We rewrite V (D,G) = Ex∼Pd [E logD(x + )] + Ez∼Pz [E log(1 − D(G(z)+ ))] = Ex∼Pd∗ logD(x)+Ex∼Pg∗ log(1−D(x)). Given a fixed G, the optimal discriminator is D∗(x) = pd∗ (x)pd∗ (x)+pg∗ (x) according to Arjovsky & Bottou (2017). Training G is to minimize V (D
∗, G). By using the same argument as Goodfellow et al. (2014), one can see that training G is equivalent to minimizing the Jensen-Shannon divergence dJS(Pd∗ , Pg∗ ). Appendix D.2 shows√
dJS(Pd∗ , Pg) ≤ √ dJS(Pd∗ , Pg∗ ) + √ o(σ) (27)√
dJS(Pd, Pg∗ ) ≤ √ dJS(Pd∗ , Pg∗ ) + √ o(σ) (28)
where o(σ) satisfies lim σ→0 o(σ) σ = 0. They suggest that for a fixed σ, minimizing dJS(Pd∗ , Pg∗ ) implies minimizing both dJS(Pd, Pg∗ ) and dJS(Pd∗ , Pg). The same behavior can be shown for many other GANs. Lemma 4. Let Jx(f) be the Jacobian of f(x) w.r.t its input x. Assume the density functions pd and pg are differentiable everywhere in Zx. For any x ∈ Zx, 1. [pd∗ (x)− pg(x)]2 +O(σ2) = [pd(x)− pg(x) + o(σ)]2 + σ2Eu [ uTJTx (pd)Jx(pd)u ] .
2. [pd(x)− pg∗ (x)]2 +O(σ2) = [pd(x)− pg(x)− o(σ)]2 + σ2Eu [ uTJTx (pg)Jx(pg)u ] .
3. [pd∗ (x)−pg∗ (x)]2+O(σ2) = [pd(x)−pg(x)+o(σ)]2+σ2Eu [ uTJTx (pd − pg)Jx(pd − pg)u ] .
Lemma 5. If u ∼ N (0, I) then Eu [ uTATAu ] = trace(ATA) = ||A||2F for any given matrix A.
The proof of Lemma 4 appears in Appendix D.3, while Lemma 5 comes from (Avron & Toledo, 2011; Hutchinson, 1989). Lemmas 4 and 5 are really helpful to interpret some nontrivial implications.
When training G, we are trying to minimize the expected norms of the Jacobians of the densities induced by D and G. Indeed, training G will minimize dJS(Pd∗ , Pg∗ ), and thus also minimize dJS(Pd, Pg∗ ) and dJS(Pd∗ , Pg) according to (27) and (28). Because √ dJS is a proper distance, minimizing dJS(Pd, Pg∗ ) leads to minimizing Ex∼pd [(pd(x)− pg∗ (x))2]. Combining this observation with Lemma 4, we find that training G requires both Ex∼pd [(pd(x) − pg(x) + o(σ))2] and Ex∼pdEu[uTJTx (pg)Jx(pg)u] to be small. As a result, Ex∼pg [||Jx(pg)||2F ] should be small due to Lemma 5. A larger σ encourages a smaller Jacobian norm, meaning the flatter learnt distribution. A small σ enables us to learn complex distributions. The optimal D∗(x) = pd∗ (x)pd∗ (x)+pg∗ (x) suggests that a penalty on Jx(pg) will lead to a penalty on the Jacobian of D.
It is also useful to observe that adding noises to real data (x) only will require dJS(Pd∗ , Pg) to be small, whereas adding noises to fake data (G(z)) only will require dJS(Pd, Pg∗ ) to be small. Lemma 4 suggests that adding noises to real data only does not make any penalty on pg . Further, if noises are used for both real and fake data, we are making penalties on both Jx(pg) and Jx(pd−pg). Note that a small Jx(pd − pg) implies Jx(pd) u Jx(pg). As a consequence, training GAN by the loss (26) will require both the zero-order (pg) and first-order (Jx(pg)) informations of the fake distribution to match those of the real distribution. This is surprising. The (implicit) appearance of the first-order information of pd can help the GAN training to converge faster, due to the ability to use more information from pd. On the other hand, the use of noise in (26) penalizes the first-order information of the loss, and hence can improve the generalization of D and G, following Theorem 8.
Connection to data augmentation: Note that each input for D in (26) is perturbed by an . When has a small norm, each x′ = x + is a local neighbor of x. Noise is a common way to make perturbation and can lead to stability for GANs (Arjovsky & Bottou, 2017). Another way to make perturbation is data augmentation, including translation, cutout, rotation. The main idea is to make another version x′ from an original image x such that x′ should preserve some semantics of x. By this way, x′ belongs to the neighborhood of x in some senses, and can be represented as x′ = x+ for some . Those observations suggest that when training D and G from a set of original and augmented images (Zhao et al., 2020a;b), we are working with an empirical version of (26). Note that our proofs for inequalities (27, 28) and Lemma 4 apply to a larger contexts than Gaussian noise, meaning that they can apply to different kinds of data augmentation.
Some recent works (Karras et al., 2020a; Tran et al., 2021) show that data augmentation (DA) for real data only will be problematic, meanwhile using DA for both real and fake data can significantly improve GANs (Zhao et al., 2020a;b; Karras et al., 2020a). Lemma 4 agrees with those observations: DA for fake data only poses a penalty on Jacobian of pg only, while DA for real data only does no penalty on pg . Differrent from prior works, Lemma 4 shows that DA for both real and fake data poses a penalty on Jx(pg) and requires Jx(pg) u Jx(pd). In other words, DA requires the zero- and first-order informations of pg to match those of pd, while also penalizes the first-order information of the loss for better generalization of D and G. This is surprising.
Appendix E presents our simulation study. The results show that both DA and Gaussian noise can penalize the Jacobians of D,G and the loss, hence confirming the above theoretical analysis.

heading: D.1 LOCAL LINEARITY
text: Consider a function f : Rn → R which is differentiable everywhere in its domain. f is also called locally linear everywhere. Let = σu, where u follows a distribution with mean 0 and covariance matrix I , σ ≥ 0, Jx(f) be the Jacobian of f w.r.t its input x. Considering f(x+ ) = f(x+σu) as a function of σ, Taylor’s theorem allows us to write f(x+σu) = f(x)+σJx(f)u+o(σ). Therefore,
E [f(x+ )] = E [f(x) + σJx(f)u+ o(σ)] (29) = f(x) + o(σ) + σEu[Jx(f)u] (30) = f(x) + o(σ), (31)
where we have used Eu[Jx(f)u] = 0 due to Eu[u] = 0 and the independence of the elements of u. As σ → 0, we have E [f(x+ )]→ f(x).

heading: D.2 PROOFS FOR INEQUALITIES (5, 6)
text: Consider the Jensen-Shannon divergence dJS(Pd∗ , Pg∗ ). Since √ dJS is a proper distance, we have the following triangle inqualities:√ dJS(Pd∗ , Pg) ≤ √ dJS(Pd∗ , Pg∗ ) +
√ dJS(Pg∗ , Pg) (32)√
dJS(Pd, Pg∗ ) ≤ √ dJS(Pd∗ , Pg∗ ) + √ dJS(Pd∗ , Pd) (33)
Next we will show that dJS(Pg∗ , Pg) = o(σ). The following expression comes from a basic property of Jensen-Shannon divergence:
dJS(Pg∗ , Pg) = H
( Pg∗ + Pg
2
) − 1
2 H(Pg∗ )−
1 2 H(Pg), (34)
where H(P ) denotes the entropy of distribution P .
Denote o(·), o1(·), o2(·), o3(·) be some functions of σ satisfying lim σ→0 o(σ) σ = 0. Appendix D.1 suggests that pg∗ (x) = E [pg(x+ )] = pg(x)+o1(σ) and log(pg(x)+o1(σ)) = log(pg(x))+o2(σ) by using Taylor’s theorem for σ. Therefore:
−1 2 H(Pg) = 1 2
∫ pg(x) log pg(x)dx. (35)
−1 2 H(Pg∗ ) = 1 2
∫ pg∗ (x) log pg∗ (x)dx = 1
2
∫ pg∗ (x) log[pg(x) + o1(σ)]dx
= 1
2
∫ pg∗ (x)[log pg(x) + o2(σ)]dx
= 1
2
∫ pg∗ (x) log pg(x)dx+ 1
2 o2(σ). (36)
H
( Pg∗ + Pg
2
) = − ∫ pg∗ (x) + pg(x)
2 log
( pg∗ (x) + pg(x)
2
) dx
= − ∫ pg∗ (x) + pg(x)
2 log
( 2pg(x) + o1(σ)
2
) dx
= − ∫ pg∗ (x) + pg(x)
2 log
( pg(x) + 1
2 o1(σ)
) dx
= − ∫ pg∗ (x) + pg(x)
2
[ log pg(x) + 1
2 o3(σ)
] dx
= −1 2
∫ [ pg∗ (x) + pg(x) ] log pg(x)dx− o3(σ)
4
∫ [pg∗ (x) + pg(x)]dx
= −1 2
∫ [ pg∗ (x) + pg(x) ] log pg(x)dx− 1
2 o3(σ)
= −1 2
∫ pg∗ (x) log pg(x)dx− 1
2
∫ pg(x) log pg(x)dx− 1
2 o3(σ) (37)
From equations (34, 35, 36, 37) we can conclude dJS(Pg∗ , Pg) = o(σ). Similar arguments can be done to prove dJS(Pd∗ , Pd) = o(σ). Combining those with (32) and (33), we arrive at
√ dJS(Pd∗ , Pg) ≤ √ dJS(Pd∗ , Pg∗ ) + √ o(σ) (38)√
dJS(Pd, Pg∗ ) ≤ √ dJS(Pd∗ , Pg∗ ) + √ o(σ). (39)

heading: D.3 PROOF OF LEMMA 13
text: For any x ∈ Zx, it is worth remembering that pd∗ (x) = E [pd(x+ )]. Consider Y = pd(x+ )− pg(x) = pd(x+ σu)− pg(x),
which is a function of u. Since u follows a distribution with mean 0 and covariance which is the identity matrix, Y is a random variable. Due to pd(x+ ) = pd(x)+σJx(pd)u+o(σ) from Appendix D.1, we can express the variance of Y as
Var(Y ) = Eu(Y 2)− (Eu(Y ))2 (40) = Eu [ (pd(x+ )− pg(x))2 ] − [Eu(pd(x+ )− pg(x))]2 (41)
= Eu [ [pd(x)− pg(x) + o(σ) + σJx(pd)u]2 ] − [pd∗ (x)− pg(x)]2 (42)
= Eu [ (pd(x)− pg(x) + o(σ))2 ] + 2σ[pd(x)− pg(x) + o(σ)]Eu[Jx(pd)u]
+σ2Eu [ uTJTx (pd)Jx(pd)u ] − [pd∗ (x)− pg(x)]2 (43)
= [pd(x)− pg(x) + o(σ)]2 + σ2Eu[uTJTx (pd)Jx(pd)u]− [pd∗ (x)− pg(x)]2 (44)
Since pg(x) does not depend on = σu, we have Var(Y ) = Var(pd(x + )) = Var(pd(x + σu)) which is bounded above by CVar(σu) = Cσ2, for some C ≥ 0. Combining this with (44) will result in
[pd∗ (x)− pg(x)]2 + Cσ2 ≥ [pd(x)− pg(x) + o(σ)]2 + σ2Eu[uTJTx (pd)Jx(pd)u] (45) completing the first statement. The second and third statements can be proven similarly.

heading: E EVALUATION OF DATA AUGMENTATION FOR GANS
text: There is a tradeoff in data augmentation. Making augmentation from a larger region around a given image implies a larger σ. Lemmas 13 and 14 suggest that the Jacobian norms should be smaller, meaning the flatter learnt distributions. Hence, too large region for augmentation may result in underfitting. On the other hand, augmentation in a too small region (a small σ) allows the Jacobian norms to be large, meaning the learnt distributions can be complex. As σ → 0, no regularization is used at all.
This section will provide some empirical evidences about those analyses. We first evaluate the role of σ when doing augmentation by simple techniques such as translation. We then evaluate the case of augmentation by adding noises. Two models are used in our evaluations: Saturating GAN (Goodfellow et al., 2014) and LSGAN (Mao et al., 2017).

heading: E.1 EXPERIMENTAL SETUPS
text: The architectures of G and D are specified in Figure 1, which follow http://github.com/ eriklindernoren/PyTorch-GAN/blob/master/implementations/gan/gan. py. We use this architecture with Spectral normalization (Miyato et al., 2018) for D in all experiments of GAN and LSGAN. Note that, for LSGAN, we remove the last Sigmoid layer in D.
We use MNIST dataset which has 60000 images for training and 5000 images for testing. During the testing phase, 5000 new noises are sampled randomly at every epoch/minibatch to compute some metrics. For the derivative of D with respect to its input, the input includes 2500 fake images and 2500 real images. Before fetching into D, both real and fake images are converted to tensor size (1, 28, 28), rescaled to (0, 1) and normalized with mean = 0.5 and std = 0.5. The noise input of G has 100 dimensions and is sampled from normal distribution N (0, I). We use Adam optimizer with β1 = 0.5, β2 = 0.999, lr = 0.0002, batchsize = 64.
E.2 THE ROLE OF σ FOR DATA AUGMENTATION
In this experiment, the input of D which includes real and fake images are augmented using translation. The shifts in horizontal and vertical axis are sampled from discrete uniform distribution within interval [−s, s], where s = 2 corresponds to σ = √ 2, s = 4 corresponds to σ = √ 6.67, and s = 8 corresponds to σ = √ 24.
Jacobian norms of D and loss V : Figure 2 shows the results. It can be seen from the figure that the higher σ provides smaller Frobenius norms of Jacobian of both D and V . Such behaviors appear in both GAN and LSGAN, which is consistent with our theory.
Jacobian norms of G: To see the effect of data augmentation on G, we need to fix D when training G. Therefore we did the following steps: (i) train both G and D for 100 epochs, (ii) then keeping D fixed, we further train G to measure its Jacobian norm along the training progress. We chose σ ∈ { √ 6.67, √ 14, √ 24} and augmented 64, 96, 128 times for each image respectively.
Figure 3 shows the results. We observe that a higher σ provides smaller Jacobian norm of G. Interestingly, as the norm decreases as training G more, suggesting that G gets simpler.

heading: E.3 AUGMENTATION BY ADDING NOISES
text: In this experiment, the input of D which includes real and fake images are augmented by adding Gaussian noise N (0, σ). We choose σ ∈ {0.01, 0.1, 0.5} and augment {16, 64, 128} times for each image respectively.
Jacobian norms of D and loss V : Figure 4 shows the results after 500 epochs. It can be seen from the figure that the higher σ provides smaller Jacobian norms. This is consistent with our theoretical analysis. In comparison with using translation, adding Gaussian noise makes the Jacobian norms in both GAN and LSGAN more stable.
Jacobian norms of G: We did the same procedure as for the case of image translation to see how large the norm of ∂G/∂z is. We choose σ ∈ {0.5, 2, 4}. Figure 5 show the results. The same behaviour can be observed. Larger σ often leads to smaller norms. It is worth noting that the Jacobian norm will be zero as σ is too large. In this case both D and G may be over-penalized. Those empirical results support well our theory.

heading: F EVALUATION OF SPECTRAL NORMALIZATION
text: This section presents an evaluation on the effect of Lipschitz constraint by using spectral normalization (SN) (Miyato et al., 2018). We use Saturating GAN and LSGAN with four scenerios: no penalty; SN for G only; SN for D only; SN for both D and G. The setting for our experiments appears in subsection E.1.
The results appear in Figure 6. When no penalty is used, we observe that the gradients of the loss tend to increase in magnitude while both D and G are hard to reach optimality. When SN is used
for G, it seems that G has been over-penalized since the gradient norms are almost zero, meaning thatGmay be underfitting. This behavior appears in both GAN and LSGAN, and was also observed before (Brock et al., 2019). The most sucessful case is the use of SN for D only. We observe that both players seem to reach the Nash equilibrium. The gradient norms of the loss are relatively stable and small in the course of training, while the quality of fake image (measured by FID) can be better than the other cases. Furthermore both the loss Vg and ‖∂Vg/∂z‖F of the generator are stable and belong to small domains, suggesting that the use of SN for D can help us to penalize the zero- and first-order informations of the loss.
Our experiments suggest three messages which agree well with our theory in Theorem 8. Firstly, when no penalty is used, the Lipschitz constant of a hypothesis may be large in order to well fit the training data. In this case the generalization may not be good. Secondly, we can get stuck at underfitting if a penalty on Lipschitzness is overused. The reason is that a heavy penalty can result in a small Lipschitz constant (thus simpler hypothesis), meanwhile a too simple hypothesis may cause a large optimization error. Hence, the generalization is not good in this case. Thirdly, when an appropriate penalty is used, we can obtain both a small Lipschitz constant and small optimization error which lead to better generalization.

heading: G FURTHER DISCUSSION
text: We have discussed both generalization and consistency in Section 3. We next provide some interpretations from our theoretical results which may be helpful in practice.
• We may want to find an unknown (measurable) function η(x) based on a training set S of size m.3 A popular way is to select a family H (e.g., an NN architecture) and then do training on S to obtain a specific ho ∈ H. The quality of ho can be seen from different levels (Bousquet et al., 2004):
E1. Optimization error: erro(ho, h∗m) = F (P̂x, ho) − F (P̂x, h∗m) for comparing with h∗m = argminh∈H F (P̂x, h) which is the best inH for the training data;
E2. Generalization gap: errg(ho) = |F (Px, ho) − F (P̂x, ho)| to see the difference between the empirical and expected losses of ho; E3. Consistency rate: errc(ho, h∗) = F (Px, ho)−F (Px, h∗) for comparing with the best function h∗ = argminh∈H F (Px, h) inH;
E4. Bayes gap: errB(ho, η) = F (Px, ho)− F (Px, η) for comparing with the truth. • A small optimization error may not always lead to good generalization. • A small generalization gap is insufficient to explain a high success in practice. Indeed, errg(ho) can be small although both empirical and expected losses are high. The use of this quantity poses a long debate (Nagarajan & Kolter, 2019; Negrea et al., 2020).
• From Theorem 1, one may try to penalize the Lipschitz constant of the loss as small as possible to ensure a small generalization gap. However, as explained before, such a naive application may not lead to good performance. The reason is that familyHmay be much smaller and the members of H will have lower capacity as L decreases. Note that a large decrease of capacity easily leads to underfitting, and hence F (Px, ho) will be high. Our experiments in Appendix F provide a further evidence when spectral normalization is overused.
• Those observations suggest that making only optimization or generalization gap small is not enough. Both should be small, and so is consistency rate due to Lemma 1.
• When does a small consistency rate still lead to bad generalization? In those bad cases, the Bayes gap errB(ho, η) will be large. Note that errB(ho, η) = errc(ho, h∗) + erra(H), where erra(H) = F (Px, h∗) − F (Px, η) is often known as the approximation error and measures how well can functions in H approach the target (Bousquet et al., 2004). Therefore erra(H) represents the capacity of family H. A stronger family with higher-capacity members will lead to smaller F (Px, h∗) and hence a smaller erra(H). Those observations imply that, provided loss f is not a constant function, a bad generalization with a small consistency rate happens only whenH has low capacity.
• When working with a high-capacity familyH, a small consistency rate is sufficient to ensure good generalization. Lemma 1 suggests that it is sufficient to ensure good generalization by making both optimization error and generalization gap to be small.
• For overparameterized NNs, we often observe small (even zero) optimization error. Our results in Theorem 3 shows that Dropout and spectral normalization can produce small generalization gap. By combining those observations, we can conclude that Dropout DNNs and SN-DNNs can generalize well.
3For simplicity, we limit the discussion to measurable functions.

Review summaries:
This paper analyzes the generalization and the consistency of a function with Lipschitz continuity. In particular, the generalization and consistency bounds of Neural Networks (NNs) with Dropout or Spectral Normalization are derived. The number of layers is logarithmic in sample size. Furthermore, the generalization of a GAN, whose discriminator and generator are both Lipschitz continuous, is given.  

This paper's primary focus is to provide insights into the relation between Lipschitz-continuity and the generalization of DNNs.  Compared to previous work, tighter bounds connecting the Lipschitz-constant of the "loss" and the expected loss of the learned function are provided. The paper also provides insights into why SN and Dropout improve generalizability in DNNs. Some quite insightful theorems connecting the generalizability of GANs to various empirical tricks commonly used to improve their performance are also provided. 

The authors provide generalization bounds on GANs and some DNNs in terms of the Lipschitz continuity of the networks and loss functions. These bounds show that by decreasing the Lipschitz constant of the networks and loss functions, one can generalize better. Moreover, they show that with dropout and spectral normalization, one can escape the curse of dimensionality in terms of generalization error. Finally, they claim that this theory supports the empirical results we see when GANs which use Lipschitz penalization (e.g., WGAN, GP-WGAN, SN-GAN, etc.) perform well in practice.

The paper tries to bound the generalization error of deep learning models and generative adversarial networks with the Lipschitz coefficient of the model. The main idea supported by the paper's discussion is that bounding the Lipschitz constant of the neural networks will lead to good generalization performance. The paper observes the connection between spectral normalization and norm-bounded dropout with the Lipschitz coefficient of the neural network and extends the proven bounds to those regularization methods.