Generalization of GANs and overparameterized models under Lipschitz continuity
Authors: Khoat Than
Nghia Vu
Venue: ICLR 2022 Submitted (2022)

Abstract: Generative adversarial networks (GANs)  are really complex, and  little has been known about their generalization. The existing learning theories lack efficient tools to analyze generalization of GANs. To fill this gap, we introduce a novel tool to analyze generalization: Lipschitz continuity. We demonstrate its simplicity by showing generalization and consistency of overparameterized neural networks. We then use this tool to derive Lipschitz-based generalization bounds for GANs. In particular, our bounds show that penalizing the zero- and first-order informations of the GAN loss will improve generalization. Therefore, this work provides a unified theory for answering the long mystery of why imposing a Lipschitz constraint can help GANs to generalize well in practice. 

Under review as a conference paper at ICLR 2022
GENERALIZATION OF GANS AND OVERPARAMETER- IZED MODELS UNDER LIPSCHITZ CONTINUITY
Anonymous authors Paper under double-blind review
ABSTRACT
Generative adversarial networks (GANs) are so complex that the existing learning theories do not provide satisfactory explanation for why GANs have great suc- cess in practice. The same situation also remains largely open for deep neural net- works. To fill this gap, we introduce Lipschitz theory to analyze generalization. We demonstrate its simplicity by showing generalization and consistency of over- parameterized neural networks. We then use this theory derive I Lipschitz-based 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 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.
INTRODUCTION
In Generative Adversarial Networks (GANs) (Goodfellow et al., 2014), we want to train a discrimi- nator D and generator G by solving the following problem:
min max En log (Dx))) + Ez-P, log(1 D(G(=)))
G D
where Pa is a data distribution that generates real data, and P3 is some noise distribution. G is mapping that maps noise: z to point in the data space. After training, G can be used 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. (020b) can train 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- bounds (Arora et al. 2017] Zhang et al. 2018 Jiang al. [2119] Husain et al.] 2019) is the strong dependence on the capacity of the family, which detines the distance between two distributions, sometimes leading to trivial bounds. This limitation prevents from fullly understanding and identifying the key factors that contribute to the generalization of GANs. For example, it has long been theoretically unclear why Lipsehitz constraint empirically can lead to great success GANs?
The standard learning theories suffer from various difficulties when analyzing overparameterized neural networks (NNs). For example, Radermacher-basee bounds (Bartlett Mendelson, 2002. Golowich et al. 2020) can be trivial (Zhang et al.) 2021); algorithmic stability (Shalev-Shwarz, jet 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 & Szepesvári
2021 Di at. 2021 Hu al. 2021 Jacot et al. 2018). has

---

Under review as a conference paper at ICLR 2022
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:
We introduce Lipschitz theory to analyze generalization of learned function. This theory is surprizingly simple to analyze various complex models in general settings (including supervised, unsupervised, and adversarial settings).
> We show that Dropout or ity. 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 significant step
neural networks avoid the curse of dimensional-
toward answering the open theoretical issues of deep learning (Zhang et al. 2021 Fang et al. 2021
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 con- necting Lipschitz continuity with generalization, and some analyses about deep neural networks. In Section we analyze the generalization of GANs in various aspects. Section concludes the paper.
2 RELATED WORK
Generalization in GANs: There are few efforts to analyze the generalization for GANs us- ing the notion of neural distance, dp(Pa, Pg), which is the distance between two distribu- tions (Pa, Pg), where D is the discriminator family[] [T] Arora et al. (2017) analyze generaliza- tion by bounding the quantity Idp(Pa,PP) - (Pp(Pa Py)l. where (Pa, Pa) are empirical ver- sions of (Pa, Pg). For a suitable choice of the loss ((Pa. Pz. D, G) in GANs, we can write (do(Pa, Pa) - do( Pa, Py) = maXDeD V(Pa, Pz, G)
DED V(Pa, P., D, G)), where Pa is the induced distribution by putting samples from P. through generator G. Both/AAora et al. (017))
and Husain et al. 2019) analyze maxpep V(a,, P. D. Go) maXDeD V(Pa, P.. D. G.) to
generalization of a trained Go,, while (Zhang et al., 2018 Jiang et al. 2019) provide upper bounds
for MaXDeD (Pa,, Pe, G) mingeg max ((Pa, Ps. D, G) Note that those quantities of interest are non- -tandaand in terms of learning theory.
A major limitation of those eestance-based bounds (Arora et al. 2017 Zhang et al. 2018 Jiang al. 2019 Husain et al. (019)) is the dependence on the notion of distance dp(:;) which relies on the best D E 'D for measuring proximity between two distributions. The distance between two given distributions (11, 2/) may small even when the two are far away (Arora et al. 2017). This because there exists perfect discriminator D, whenever and v 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 insufficiint to understand generalization of GANs.
Qi (2020) shows generalization bound for their proposed Loss-Sensitive GAN. Nonetheless,
nontrivial to make their bound to work with other GAN losses. Wu et al. (2019) show that the discriminator will generalize 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.
In 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.
2

---

Under review as a conference paper at ICLR 2022
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 al.] [0188 Lucie al. 20118] Mescheder et al. 2018 Kurach et al., [019] Jenni & Favaro 2019 Wu et al. 2019 Zhou et al., 2019] |020] Chu et al.,
2020). Gradient penalty (Gulrajani al., 2017) and spectral normalization (Miyato al. 2018)
two popular techniques to constraint the Lipschitz continuity of D or G w.r.t their inputs. Some other
works (Mescheder 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.] 20200 Tran et al.) (02T). Those works empirically found that Lipschitz continuity can help improving stability and generalization of GANs. However, it has long
provides an unified explanation explanation.
been a mystery of why imposing Lipschitz constraint can help GANs to generalize well. This work
LIPSCHITZ CONTINUITY AND GENERALIZATION
In this section, 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.
Consider a learning problem specified by a function/hypothesis class H. an instance set X' with diameter at most B, and loss function f : H. X + R which is bounded by a constant C. Given a distribution Pa defined on X, the quality of a function l((x) is measured by its expected loss F(Pa, h)) Eg- [J,,,, ar). Since P, is unknown, we need to rely on finite training sample S = [-1,,..,, Im] C X and often work with the empirical loss F ((2,.h) = Ez-P, (h,, x)] = 1 Eass f(h, 2),, where Pz the empirical distribution defined on S. A learning algorithm will m
Notations:
pick function hi. E H based on input S, i.e., hm - S).
We first establish the following result whose proof appears in Appendix A
Theorem 1 (Lipschitz continuity + Generalization). If a loss fh, is L-Lipschitz continuous w.r input x in compact set X c for any E H. and Pg is the empirical distribution defined from m i..dd samples from distribution Pa, then sup (F(Pa, F(P,,, h)) upper-bounder by kEH
1. LA + CV(BB==>> log 4 2 log 6)/m with probability at least 8, for any constants 8E E (0, 1] and X E (O,B). (LB + 2Cmmm -o/nz with probubility at least 2 2ee2exxxxx000 ). any a S ng/(2 + nz))-
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, Cross- entropy 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. 202T) propose to put a penalty on the Lipschitz constant of only. However, leaving open the Lipschitzness of f w.r.t f may not ensure small Lipschitz constant of the loss.
This theorem tells that Lipschitz continuity is the key to ensure a function to generalize. Its gen- eralization bounds can be better the Lipschitz constant of the loss decreases. Note that there is a tradeoff between the Lipschitz constant and the expected loss F(Pz, h) of the learnt function. A smaller L means that both f and h are getting simpler and flatter, and hence may increase F(P,, h). In contrast, a decrease of F(P., h) may require h to be more complex and hence may increase T..
Theorem I presents generalization bounds, in general setting, which suffer from the curse of dimensionality. ity. This limitation is common for any other approaches without further assumptions Bach 2017). For some special classes, we can overcome this limitation discussed next.
3.1 DEEP NEURAL NETWORKS THAT AVOID THE CURSE OF DIMENSIONALITY
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. provides sharp bounds for the Lipschitz constant.
3

---

Under review as a conference paper at ICLR 2022
Let fixed activation ffucciono (o1..... σK). where og is Pı-Lipschitz continuous. Let be the neural network associated with weight matrices (W...... W WR), and Ln, be the Lipschitz constant of h. Let the bounds ($1...., sK) and
Theorem 2.
hw(a) == OK (Wxok-1(WK-1-
T1
(b1,...,bx .b) be given.
Spectrallynorrmaiizer networks (SN-DNN): Let Han (hw W = (W1 Wk), WWll S
sr), where || lllo is the spectral norm. Then 4h E Hons In S II I Pk-8k-
Dropout DNN: Let Har (lo a lww (rw( q), [[Wilr I bi), where DrT is the usual dropout training (Srivastava et al. 2014) with drop rate forrr network lww, and I1-11 is the Frobenius norm. Then 4h E Har. La S IIk= PRbE.
Most popular activation functions (c.g., ReLU, Leaky ReLU, Tanh, SmoothReLU, Sigmoid, and Softmax) have small Lipschitz constants (px S 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 9
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, c.g. by using spectral normalization. The Lipschitz constant will be exponentially smaller as the neural network deeper and the spectral norm at each layer is smaller than 1. This case often happens as observed by Miyato et (2018).
The generalization of SN-DNNs and Dropout DNNs can be seen by combining Theorems and One can observe that, for the same norm bound on weight matrices, network with smaller Lipschitz constant can provide a better bound. An interesting implication from Theorem 2 that deeper networks (larger K) will have smaller Lipschitz constants and hence lead to better generalization bounds. This answers the second question of Section [
2 will result in a bound of (( (mm=)//) which suffers from the curse of dimensionality. The following theorem shows stronger results in Appendix A.I
trivial combination of Theorems I and 2
Theorem 3 (Generalization of DNNs). Given the assumptions in Theorems 7 and 2
let Ly be the
Lipschitz constant of the loss f(,, x) w.r. h, and å (0, 1] be any given constant.
1. SN-DNNs: assume that there exist E (0, 1) and constant Can such that Cemp 2 I Pk
If the number of layers K 2 - log, m, then the following holds with probability at least
Su [F(P,,h) F() S (CanLy B + CV/lo 2log 6) m 0.5
2. Dropout DNNs: For Har with drop rate (0, 1), let Car = IT
k= Pkbn. If the number of layers K= 2 - log, m, then the following holds with probability at least 1 - 8:
SリрдeНa. [F(P,, h) - ((P S BCaaLL + Cylog 4 - 2og 6) m 0.5
The assumption of K > - log, m is naturally met in practice. For example, when training from 1.2M images, constant = 0.5 requires K 2 10, and q = 0.1 requires K x 3. Note that Alexnet (Krihhessky al.] 2012) has 8 layers and the generator of StyleGAN (Karras al. (021] has 18 layers. The assumption about SN-DNNs can be satisfied when choosing activations with Lipschitz constant Pk < 1 or ensuring the spectral bound 8&
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 al. 2018) provide generalization bounds for SN-DNNs for classification problems, using Radermacher com- plexity or PAC-Bayes. One major limitation of their works is that the sample size depends poly- nomiallylexponentialyy on depth K. For SN-DNNs using ReLU, Golowich et al. (2000) improved the dependence to be linear K if provided assumptions comparable with ours. In another view, when fixing m. their results require K = (mm) to get a meaningful generalization bound. This impractical. In contrast, our result shows that it is sufficient to choose K which logarithmic in m. Another limitation of the bounds in (Bartlett et al. 2017 Neyshabur al. 2018 Golowich ct al. 2020) is the dependence on 1/7, where 7 is the margin of the classification problem. Note that practical data may have very small margin or may be inseparable. Hence those bounds are really limited and inapplicable to inseparable cases. On the contrary, Theorem 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 -fate-of-the-art studies about Dropout (Arora et al. 2021 Mianjy & Arora 2020
4

---

Under review as a conference paper at ICLR 2022
Mou et al. 2018) obtain efficient bounds only for networks with 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.
3.2 CONSISTENCY OF OVERPARAMETERIE MODELS
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 explain high performance, since both losses may be large despite their small difference. Next we consider consistency (Shalev- Shwartz et al., 2010) to see the goodness of a function compared with the best in its family.
Definition 1. A learming algorithm A is said to be Consistent with rale conns (m) under distribution Pz for all m, Ess-p= P(Pg.
A(H, S) F(P,, h+ S <cons (m), where ccons (m) must satisfy Coons (m) + as m + oC, h" arg min F(2,, h).
Consistency says that, for any (but fixed) m. the learned function Am AAH,, is required to be (in expectation) close to the optimal ht.. The closeness is measured by [F[ hm) - F(P2. 2: ]-
By considering this quantity, optimization error will naturally appear. We first show the following observation in Appendix
Lemma 1. Denote h- arg minNER F(P2, and Pz. is the empirical distribution defined from sample S of size m. For any ho E H. letting e, F F(Pa, 2, ho) minncH F(Pa, h), we have: [F(Pa, ho) - F(P,,h")) S en + 2suPReH [F h) F(P,,))
This lemma shows why the optimization error e, and capacity of family H control the goodness of a function. Combining Theorem [ with Lemma will lead to the following.
Theorem (General family). Given the assumptions in Theorem
7 consider any function ho E H.
Let h = arg minkeH F(Pz,)) h)) and 6 = F(Pz, ho)) - min F(P,,h) h)) be the optimization error of ho on sample S of size m. For any a S n nz), with probability at least 1 [F(P,, ho) F(Pa, hi)) S e, + 2LB 2C)m
2 texp(-0.5m
Corollary 1. Given the ussumptions in Theorem + consider learning algorithm A and family H. A is consistent if. for any given sample of size m, the learned function ho = A(H, S) has optimization error at most (m) which is a decreasing function of m, i.e. (m) + 0 as
cc.
The assumption about optimization error e., (m) ) is naturally satisfied when the training problem is
convex. Indeed, is well-known FAllen-Zhu 2017 Schmidt al., 2017) that gradient descent (GD)
with 7' iterations can find a solution with сπтоr O whereas stochastic gradient descent (SGD)
with I' iterations can find solution with error 0..5. Therefore, GD and SGD with T (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 OTT--.5). Those results suggests that T = (mm) iterations are sufficient to ensure our assumption about (mm) Allen-Zhu et al. 2019) show that T Olog m.) iterations are sufficient ensure (m) 0(m )
Combining Theorems 3 with Lemma D 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 h, E Har- Let h- arg minneHa. F(P2, h). and E, F(Pa, ho) mink F(Pa,h) be the optimization
error of ha on a sample S of size m. For any constant 5 E (0, 1), with probability at least 1 5: [F ha) - F(P,, S 6, + (CarLs B + Colog 4 - 2 log m -0.5
Corollary 2 (Consistency of Dropout DNNs), Given the assumptions in Theorem 5 consider learning algorithm A and family Har. If, for any given sample S of size m. the learned function ho A(Har, S) has optimization error at most (mm) which a decreasing function of m, then A is consistent with rate (o(m) (Car I. B O-log 4 2 log o) m -0..
5

---

Under review as a conference paper at ICLR 2022
Connection overparamettrizzation Contrary to classical wisdoms about overfitting, modern ma- chine learning exhibits a strange phenonmenon: very rich models such as neural networks are trained to exactly fit (i.e., interpolate and c, = 0) the data, but often obtain high accuracy test data (Belkin et al. 2019; Zhang et al., 202T). Those models often belong to overparameterization regime where the number of parameters in model is far larger than m. Such strikingly strange behavior could not be explained by traditional learning theories (Zhang et al., (022I). Some works try to under- stand overparameterization in linear regression (Bartlett et al. (2020) and kernel regression (Liang et al. 2020). Some recent results (Kuzborskij & Szepesvári 2022 Ji et al., [222]] Hu et al., 2021
Jacot et allj22018 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 ((m) iterations are sufficient for GD and SGD to achieve optimization error (.(m) (m--0.) as discussed before. Combining this ob- servation with Corollary 2 will reveal consistency with rate 0(m-0.5) for Dropout DNNs and SN- DNNs. To the best of our knowledge. this is the first consistency result for overparameterized DNNs which are truly deep and avoid the curse of dimensionalityy
Why are small consistency rates for high-capacity families sufficient to guarantee high gener- alization? To see why, consider Gaps (h, 17) = F(P,. ho) - F(Px: 77 which is the Bayes gap of an ho A(H, S). where 17 denotes the (unknown) true function we are trying to learn. Note that Gaps hoo n) = Cons(ho, m) + F(P,. h²) - F(Pa, n), where Cons(ho, m) = F(Pa. ho) F(P,, h²) denotes the consistency rate. This decomposition suggests that requirement of both Cons(ho, (ho, m) and F(Pz, ht)) to be small will ensure a small Gapp (ho, 7), since F(P,, n)) is inde- pendent of H. In other words, small consistency rate for high-capacity H 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 H. of the chosen NN family so that Hg has small generalization gap. For example, Theorem 3, we originally need to work with family H {hw : ||Will S b.). but Dropout localizes subset Har C H having 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 overparameterizeed 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.
4 GENERALIZATION OF GANS
This section presents a comprehensive analysis on generalization of GANs. We then discuss why Lipschitz constraint succeeds in practice.
Notations: Let S = {xI,..., Imm :1.... ] consist of m i.idd. samples from real distribution Pa defined a compact set Z, C RT and m i..dd samples from noise distribution P. defined on compact set Z. C R=n P= and P= be the empirical distributions defined from S respectively. Denote D as the discriminator family and G as the generator family. Let v vDD, G, x; 2) = thi (D(z)) t/2 D(G(2)) be the loss defined from a real example x Pa. a noise 2 ~ Pz. a discriminator 1 E D. and a generator G E G. Different choices of the measuring functions (+), ti2) will lead to different
GANs. For example, saturating GAN (Goodfellow et al. (014)) uses t/ (x)
1/2
log(z);
WGAN (Arjovsky et al. 2017) uses t/ (xx = (2(x)) = x; LSGAN (Mao et al. 2017
2019)
uses
(x) (a + a)² U2 σ (x + b)² for some constants a, b: EBGAN (Zhao et al.
2017 uses
(1() x, 1h (x) ma r-x) for some constant We will often work with: V(Pa. P., D. G)
P., D, = (e (D(x)) (1--(()())() V(Pa, P., D) = B, v (D(x)) + E.-P, 22(11 D(G P., D) E, (D(()))) +
Ez-r, (D(x)) (11 (I
E. 22 - D(G(=)))
In practice we only have a finite sample S and an optimizer will solve mingeg maxDeD ((Pa, Pz, D.G) and return an approximate solution (Do, Go), which can be different from the training optimum (Do, G*)) and Nash solution (D*, G*), where
(D', G.) = arg min max V(Pa. D.G),, (D', ",,
arg min max ((Pa, P.. D.G) (2) GEg DED
GEG DED

---

Under review as a conference paper at ICLR 2022
In learning theory, often estimate (V(Pa, Do. -V Do. Go)) to general- ization. However a small bound on this quantity may not be enough, since V (a,, P.. D.. Go) can be far from the best V(Pa, Pz, D* G*). Another way (Bousquet al. 2004) is to see How good is (Da, Go) compared to the Nash solution (D* G*) In other words, we basically need to estimate the difference [V[Pa, Pz, Doy Go) ((Pa, P2, D", G*] (Pa,a, Pz, Da. Go) mingeg maxDeD ((Pa, PP, D, where ((Pa, Pz. Dos Go) shows the quality of the fake dis- tribution induced by generator G..
P...
We first make the following error decomposition:
V(Pa, Pz, P. -VV D. G.) -(P G.)l+
[V Do Dt G.) + P. D.. -VPa,, G*)] (3)
The first term (Pa,,, Pz. Do: G.) V(a,, Pz. Do. Go)) in the right-hand side of (3) shows the difference between the population and empirical losses of specific solution (Da, Go). The sec- ond term (Va,,, Ps. Do, Go) - ((Pa. Ps, Dū Gz) is in fact the Optimization error incurred by the optimizer. This eπror depends strongly on the capacity of the chosen optimizer. The third term (Va,,, P=, DV, G ((P,, P2, D*, ;""))) is optimizer-independent and strongly depends the pacity of both families (D, 9), since both ((Pa. P Dr, G.)) and (PP,, Pz, D", G*) ) are optimizer- independent. We call this term Joint error of (D, G). In the next subsections, we will provide upper bounds on both the error (Do: Go) and joint error of (D,9), and then generalization bounds that take the optimization error into account.
In the later discussions, we will often use the following assumptions and notation = LyL which upper bounds the Lipschitz constant of the loss vDD G, (,,
Assumption 1. 4/1 and th2 are -pp-iischhitz continuous w.r.l. their inputs on a compact domain and upper-bounded by constant C 2 O.
Assumption 2. Each generator G E G is Lg-Lishchitz continuous w.T. its input x over compact set Zg C. F. with diameter at most B,,
Assumption 3. Each discriminator D E 'D is La-Lipschitz continuous w.r. its input over compact sei 3 C Th with diameter at most By.
These assumptions are reasonable and satisfied by various GANs. For example, WGAN, LSGAN, EBGAN naturally satisfy Assumption [ while saturating GAN will satisfy it if we constraint the output of D to be in [a, (0, 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., 20206 Therefore Assumptions and 2 are natural.
4.1
ERROR BOUNDS
The following result readily comes from Theorem
Corollary 3. Given the assumptions [ 2 for any 8 E (0, A E (0, Bz), with probability at least 1 - 8, we huve
suppep.Geg P...
LA+ C B.A log 4 - 2 2log 6
mm
This corollary tells the generalization of any generator G E G. and can be further tighten by using Theorem when using SN or Dropout. To see generalization of both players (Do, G.), observe that (Va,,, Pz. Do, G.) V(P,, P., Do, Go)l S supDED, (V(Pa, Pz, D2 V(Pa, Pz, D, G) The following theorem provides an upper bound whose proof appears in Appendix [
Theorem 6. Denote c(D,g) = supDeD, Geg (V(Pa, P., D) V(Pa. P., D,G)) G)). Given the assumptions ! 3, for any constants 5, o E (0, 1].
(amityyl for any À B.). x (0, Bz), with probability at least - 8 pz: BB log 4 2log d + I Ladd + G [ X= n log 2 log 6, B
(D,9) S LA+ Vm
(D with spectral norm) given the assumptions in Theorem 3 with probability at least 1 - 28: <(Hsn; 9) < (Can Top I.g B2 2C 4 2lo + Can Lag Lug B.) 12mmmm0 -0.3
7

---

Under review as a conference paper at ICLR 2022
(D with Dropout) given the assumptions in Theorem 3 with probability at least 1 28: e(Har,9) S [CarLe + 20 + By 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 2, 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).
is worth observing that a small Lipschitz constant of the loss not only requires that both discrimi- nator 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 either D or G may be insufficient to ensure Lipschitz continuity of the loss.
One advantage of the generalization bounds in Theorem is that the upper bounds on (P Pz, D, G) V a Pz, D, G) hold true for any particular (D, G) in their families. Mean- while, the existing generalization bounds (Arora et al. 2017 Zhang et al. 2018 Diang et al. 2019 Wu et al. 2019; Husain et al. (019) hold true conditioned on the best discriminator. Hence the bounds in Theorem d are more practical than existing ones, since is not trained to optimality before training G in practical implementations of GANs.
Next we consider the joint error V(Pa. P;, V(Pa, Pz. D", G*) of both families (D, g). Such a quantity also shows the goodness of the training optimum (D", G*) compared with the Nash solution (D", ".). It is worth observing that [V Pz. Do Go) - V(Pa, D", mingeg maxDeD ([Pa. Pz. D.G) mingeg MaXDED V(Pa, P2, D, 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 7 2 3, for any constants d, 6g E (0, X E (0, BaJ. A dz: (V Pe, Do G V(a,, Ps, Dr G')l S LA+
(0, Ba), with probability least
B log 4 - 2log 5 + Lo + vm V [B_ X na log 4 2 2log dg.
C
vm
This bound on joint capacity of (D,9) 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
4.2 FROM OPTIMIZATION ERROR TO GENERALIZATION
Finally we make bidge between optimization error and generalization. The decomposition 3 contains three components, for which the first component is bounded in Theorem 66 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
7
3 and the opti-
mization error V (Pa, 6, Do, G.) min max ((Pa, P., D. G)) S 6 Denote Feone(D,
GEG DED P., G.) - ((P,, P., D*, G*),. For any constants 6, 8g E (0,
1. (General (amity) for any X E (0, B2), d E (0, Bz). with probability least 1 - ô Szi 20
Coons (Do S Co + 2LX
V log 4 2log + 2Ly +
vm
[B2 "= log 2 log
m
2. (Spectral norm) given the assumptions in Theorem
3 D Hyn with probability at least
1 25: Coone (Hams 9)= S Co + 2( L. L. Bg + 20
Tog 4 - 2lg 0 + Can Lag Ba m -0.5
3. (Dropout) given the assumptions in Theorem 3 D = Har, with probability at least 1 - 20:
6cons (Har, 9) co 2(Cas Lng I.g B2 2C log 4 2log 0 + Car Tog B,, BaJm= 0.5 -0.5
Theorems 6 and g 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-
8

---

Under review as a conference paper at ICLR 2022
ture, work reveals that GANs 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 Dropout. We believe that this property can hold for many other DNN families.
One important implication from Theorem 8 that GANs can be consistent under suitable conditions. An example condition is overparameteriizaton, for which the optimization error can be zero. Our experiments in Appendix F provide good evidence for this conjecture as the well-trained discrim- inators 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.
4.3
WHY A LIPSCHITZ CONSTRAINT IS CRUCIAL
Various works (Guo et al. 2019; Jenni& & Favaro
2019| Qi 2020 Arjovsky et al.; 2017 Guirajani
ct al.
2017
Roth et | Miyato et al. 2018
[01
Zhou et al. 2019 Thanh-Tung et al. 201 Diang
et al.
2019 Tanielian et al. 2020; Xu et al. 2020) try to ensure Lipschitz continuity of the discrim-
inator or generator. The most popular techniques are gradient penalty (Gulrajani et al. 2017) and spectral normalization (SN) (Miyato et al. 2018). Those techniques
really useful for different losses (Fedus et al.] 22013) 8) 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 al. 2019). Some recent large-scale generators (Brock 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 bj 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 [ for explanation). Those empirical observations without theory poses a long mystery of why can imposing a Lipschitz constraint help GANs to perform well? This work provides an answer:
Theorems and show that 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 (Myytto et al. 2018) is a popular technique 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 g are satisfied. Therefore the generalization bound in Theorem 8 is tight and supports well the success of spectrally-normalizze 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 al. 2017) naturally requires D to be I-Lipschitz continuous. Weight clipping is used so that every element of network weights belongs to [-c, c] for some constant c. For some 0.01 in (Arjovsky al. 2017), the spectral norm of the weight matrix at each layer can be smaller than In those cases the Lipschitz constant of D can be exponentially small, leading to tight bounds in Theorem an better generalization.
choices, e.g.
> SN, gradient penalty, and data augmentation are crucial parts of large-scale GANs (Brock et al., 2019 Zhang al. 2019 Karras et al. 20205). As result, Theorems 6 and g provide 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 bad population loss and high optimization error.
5 CONCLUSION
We have presented 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.
For 0.01, if the number of units at each layer is more than 100, then the Frohenius norm of the weight matrice each layer is smaller than and so for the spectral norm.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. The Journal of Machine Learning Research, 18(1):8194 8244, 2017.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning, pp. 242-252 252. PMLR, 2019.
Martin Arjovsky and Leon Bottou. Towards principled methods for training generative adversarial networks. In International Conference on Learning Representations, 2017.
Martin Arjovsky, Soumith Chintala, and Leon Bottou. Wasserstein generative adversarial networks. In Proceedings of the 34th International Conference on Machine Learning. 2017.
Raman Arora, Peter Bartlett, Poorya Mianjy, and Nathan Srebro. Dropout: Explicit forms and capacity control. In International Conference Machine Learning, pp. 351-361. PMLR, 2021.
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (gans). In International Conference Machine Learning, pp. 224- 232, 2017.
Haim Avron and Sivan Toledo. Randomized algorithms for estimating the trace of an implicit sym- metric positive semi-definite matrix. Journal of the ACM (JACM), 58(2) 2011.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18( (8(1):629-63) 1812 2017.
Yogesh Balaji, Mohammadmahdi Sajedi, Neha Mukund Kalibhat, Mucong Ding, Dominik Stöger, Mahdi Soltanolkotabi, and Soheil Feizi. Understanding over- paraamctttteinnnoonnn in generative ad- versarial networks. In International Conference Learning Representations, 2021.
Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-45) 2002.
Peter I. Bartlett, Dylan Foster, and Matus Telgarsky. Spectrally-normalized margin bounds for neural networks. Advances in Neural Information Processing Systems, 30:6240 6249, 2017.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(499:30033-30077) 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconeiling modern machine- learning practice and the classical varinner trade-off. Proceedings of the National Academy of Sciences, 116(32):15849 15854, 2019.
Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Introduction to statistical learning the- ory. In Machine Learning 2003, LNAI, volume 3176, pp. 169-207. Springer, 2004.
Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale gan training for high fidelity natural image synthesis. In International Conference on Learning Representations, 2019.
Casey Chu, Kentaro Minami, and Kenji Fukumizu. Smoothness and stability in gans. In Interna- lional Conference on Learning Representations, 2020.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675- 1685. PMLR, 2019.
Cong Fang, Hanze Dong, and Tong Zhang. Mathematical models of overparameterized neural networks. Proceedings of the IEEE, 10965)66337733 2021.
William Fedus, Mihaela Rosca, Balaji Lakshminarayanan, Andrew M Dai, Shakir Mohamed, and Ian Goodfellow. Many paths to equilibrium: Gans do not need to decrease a divergence at every step. In International Conference Learning Representations, 2018.
10

---

Under review as a conference paper at ICLR 2022
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. Information and Inference: A Journal of the IMA, ((2):43-5044, 2020.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Infor- mation Processing Systems, pp. 2672-2680, 2014.
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J Cree. Regularisation of neural net- works by enforcing lipschitz continuity. Machine Learning, 110(2):933416, 2021.
Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Im- proved training wasserstein gans. Advances Neural Information Processing Systems, pp. 5767-5777, 2017.
Tianyu Guo, Chang Xu, Boxin Shi, Chao Xu, and Dacheng Tao. Smooth deep image generator from noises. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 9731-3738, 2019.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, New York, NY, 2017.
Yongjun Hong, Uiwon Hwang, Jaeyoon Yoo, and Sungroh Yoon. How generative adversarial net- works and their variants work: An overview. ACM Computing Surveys (CSUR), 52(1):1-45 2019.
Tianyang Hu, Wenjia Wang, Cong Lin, and Guang Cheng. Regularization matters: A nonparamet- ric perspective on overparametrized neural network. In International Conference on Artificial Intelligence and Statistics, pp. 829-837. PMLR, 2021.
Hisham Husain, Richard Nock, and Robert C Williamson. A primal-dual link between gans and autoencoders. In Advances in Neural Information Processing Systems, volume 32, pp. 415-424, 2019.
Michael F Hutchinson. stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. Communications in Statistics Simulation and Computation, 18(3): 1059- 1076, 1989.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: convergence and gener- alization in neural networks. In Advances in Neural Information Processing Systems, pp. 8580- 8589, 2018.
Simon Jenni and Paolo Favaro. On stabilizing generative adversarial training with noise. In Pro- ceedings the 2019.
the IEEE Conference on Computer Vision and Pattern Recognition, pp. 12145-12153,
Ziwei Ji, Justin D Li, and Matus Telgarsky. Early-stopped neural networks are consistent. arXiv preprint arXiv:2 106.000000 05932, 2021.
Haoming Jiang, Zhehui Chen, Minshuo Chen, Feng Liu, Dingding Wang, and Tuo Zhao. On com- putation and generalization of generative adversarial networks under spectrum control. In Inter- national Conference Learning Representations, 2019.
Tero Karras, Miika Aittala, Janne Hellsten, Samuli Laine, Jaakko Lehtinen, and Timo Aila. Training generative adversarial networks with limited data. In Advances in Neural Information Processing Systems, 2020a.
Tero Karras, Samuli Laine, Miika Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila. Ana- lyzing and improving the image quality stylegan. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 81 10-8119, 2020b.
Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
doi:
11

---

Under review as a conference paper at ICLR 2022
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems, volume 25, pp. 1097-1105, 2012.
Karol Kurach, Mario Lučić, Xiaohua Zhai, Marcin Michalski, and Sylvain Gelly. A large-scale study regularization and normalization in gans. In International Conference on Machine Learning, pp- 3581-3590, 2019.
Jaa Kuzborskij and Csaba Szepesvári. Nonparametric regression with shallow overparameterizzed neural networks trained by gd with early stopping. In Conference on Learning Theory, pp. 2853- 2890. PMLR, 2021.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai On the multiple descent of minimum-norm interpolants and restricted lower isometry of kernels. In Conference Learning Theory, pp- 2683-2711. PMLR, 2020.
Mario Lucic, Karol Kurach, Marein Michalski, Sylvain Gelly, and Olivier Bousquet. Are gans created equal? large-scale study. In Advances in Neural Information Processing Systems, pp. 700-709, 2018.
Xudong Mao, Qing Li. Haoran Xie, Raymond YK Lau, Zhen Wang, and Stephen Paul Smolley. Least squares generative adversarial networks, In Proceedings of the IEEE International Confer- ence on Computer Vision, pp. 2792-2292220 7792-2802, 2017.
Xudong Mao, Qing Li, Haoran Xie, Raymond YK Lau, Zhen Wang, and Stephen Paul Smolley. On the effectiveness of least squares generative adversarial networks. IEEE Transactions Pattern Analysis and Machine Intelligence, 41(12):2947-266 2019.
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of gans. In Advances in Neural Information Processing Systems, pp. 1825-1835, 2017.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for gans do actually converge? In International Conference on Machine Learning, pp. 3481-3490, 2018
Poorya Mianjy and Raman Arora. On convergence and generalization of dropout training. In Ad- vances Neural Information Processing Systems, volume 33, 2020.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference on Learning Representations, 2018.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2018
Wenlong Mou, Yuchen Zhou, Jun Gao, and Liwei Wang. Dropout training, data-dependent reg- ularization, and generalization bounds. In International Conference Machine Learning, pp- 3645-3653, PMLR, 2018.
Vaishnavh Nagarajan and J Zico Kolter. Gradient descent gan optimization is locally stable. In Advances in Neural Information Processing Systems, pp. 5585-5595, 2017.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generaliza- tion deep learning. Advances in Neural Information Processing Systems, pp. 11615-11626. 2019.
Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy. In defense of uniform convergence: Generalization via derandomization with application to interpolating predictors. In Interna- tional Conference on Machine Learning, pp. 7263-7272 PMLR, 2020.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A bac-bay approach to spectrally margin bounds for neural networks. International Conference on Lear- ing Representations, 2018.
12

---

Under review as a conference paper at ICLR 2022
Quynh Nguyen. On the proof of global convergence of gradient descent for deep relu networks with linear widths. In International Conference on Machine Learning. 2021.
Quynh Nguyen and Marco Mondelli. Global convergence of deep networks with one wide layer fol- lowed by pyramidal topology. In Advances in Neural Information Processing Systems, volume 33, 2020.
Weili Nie and Ankit Patel. Towards a better understanding and regularization of gan training dy- namics, In Conference on Uncertainty in Artificial Intelligence (UAI), 2019.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural sam- plers using variational divergence minimization. In Advances in Neural Information Processing Systems, pp. 271-279, 2016.
Patricia Pauli, Anne Koch, Julian Berberich, Paul Kohler, and Frank Allgower. Training robust neural networks using lipschitz bounds. IEEE Control Systems Letters, 2021.
Guo-Jun Qi. Loss- sensitive generative adversarial networks on lipschitz densities. International Journal of Computer Viston, (28(5)1118-111 1140, 2020.
Kevin Roth, Aurelien Lucchi, Sebastian Nowozin, and Thomas Hofmann. Stabilizing training of generative adversarial networks through regularization. In Advances in Neural Information Pro- cessing Systems, pp. 2018-2028, 2017.
Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. In Advances in Neural Information Processing Systems, pp. 2234-2242, 2016.
Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn, and Jason Lee. On the convergence and ro- bustness of training gans with regularized optimal transport. In Advances in Neural Information Processing Systems, pp. 7091-7101. 2018.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2):83-112, 2017.
Shai Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-221 2670,, 2010.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research, 19(1)11929-1958 2014.
Ugo Tanielian, Thibaut Issenhuth, Elvis Dohmatob, and Jeremie Mary. Learning disconnected man- ifolds: gan's 's land. In International Conference Machine Learning, 2020.
Hoang Thanh- Thngh Truyen Tran, and Svetha Venkatesh. Improving generalization and stability of generative adversarial networks. In International Conference on Learning Representations, 2019.
Ilya Tolstikhin, Olivier Bousquet, Sylvain Gelly, and Bernhard Schoelkopf. Wasserstein auto- encoders. International Conference on Learning Representations, 2018.
Ngoc-Trung Tran, Viet-Hung Tran, Ngoc-Bag Bao Nguyen, Trung-Kien Nguyen, and Ngai-Man Che- ung. On data augmentation for gan training. IEEE Transactions on Image Processing, 30: 10:1882- 1897, 2021.
Bingzhe Wu, Shiwan Zhao, Chaochao Chen, Haoyang Xu, Li Wang, Xiaolu Zhang, Guangyu Sun, and Jun Zhou. Generalization in generative adversarial networks: A novel perspective from pri- vacy protection. In Advances in Neural Information Processing Systems, pp. 307-317, 2019.
Huan Xu and Shie Mannor. Robustness and generalization. Machine learning, 86(3):391-423, 2012.
Huan Xu, Constantine Caramanis, and Shie Mannor. Robust regression and lasso. IEEE Transac-
fions Information Theory, 56(7):351-3354, 2010.
13

---

Under review as a conference paper at ICLR 2022
Kun Xu, Chongxuan Li. Huanshu Wei, Jun Zhu, and Bo Zhang. Understanding and stabilizing gans' training dynamics with control theory. In Proceedings of the 37th International Conference on Machine Learning. 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
Han Zhang, Ian Goodfellow, Dimitris Metaxas, and Augustus Odena. Self-attention generative adversarial networks. In International Conference Machine Leurning, pp. 7354-7363, 2019.
Han Zhang, Zizhao Zhang, Augustus Odena, and Honglak Lee. Consistency regularization for generative adversarial networks. In International Conference on Learning Representations, 2020.
Pengchuan Zhang, Qiang Liu, Dengyong Zhou, Tao Xu, and Xiaodong He. On the discrimination- generalization tradeoff in gans. In International Conference on Learning Representations, 2018.
Junbo Zhao, Michael Mathieu, and Yann LeCun. Energy-based generative adversarial networks. In International Conference Learning Representations, 2017.
Shengyu Zhao, Zhijian Liu, Ji Lin, Yun Zhu, and Song Han. Differentiable augmentation for data-efficient gan training. In Advances in Neural Information Processing Systems, 2020a.
Zhengli Zhao, Zizhao Zhang, Ting Chen, Sameer Singh, and Han Zhang. Image augmentations for gan training. arXiv preprint Akiv:2000.025955 2020b.
Zhiming Zhou, Jiadong Liang, Yuxuan Song, Lantao Yu, Hongwei Wang, Weinan Zhang, Yong Yu, and Zhihua Zhang. Lipschitz generative adversarial nets. In International Conference on Machine Learning, pp. 7584-7593, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine Learning, 109(3):467-492, 2020.
14

---

Under review as a conference paper at ICLR 2022
A LIPSCHITZ CONTINUITY = GENERALIZATION
This section provides the proofs for the theorems of Section Let X - X, be partition of
X' into N disjoint subsets. We use the following definition from Xu & Mannor (2012).
Definition (Robustness). An algorithm A is (N, r-obbust xm -> IR, if the following holds for all S Xm; Vs E S, Va E X, ViE NI, if E &, then (f(AHH))), - -)A((),)) - <(().
Basically, robust algorithm will learn 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 leartt 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 Xu & Mannor 2012)). I learning algorithm A is (N, e-obbustt and the training data S is an i..dd sample from distribution Pa. then for any 8 E (0, we have the following with proba- bility at least 1 8: [F A(H, S)) - F( A(H, S)) S c(S) + CV(N log 4 2og 6)/m.
This theorem formally makes the important connection between robustness of an algorithm and generalization. an algorithm is robust, then its resulting hypotheses can generalize. One important implication of this result is that should ensure the robustness of learning algorithm. However, is nontrivial to do so general.
Let us have closer look robustness. e(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 function y X - Y is said to be L-Lipschitz continuous if d,y (x), v())))(())) < Lde( x') for any x, x' E X, where dy is metric on X' dy a metric on Y, and Z 0 is the Lipschitz constant. Therefore, we establish the following connection between robustness and Lipschitz continuity.
Lemma Given any constant > O, consider loss f H X TR where C Te compact, B = diamiX)= = maxx,x'ex' || x' z'I1xo. N 1==x-=a >== If any h E H. f(h, x)) is L-Lipschitz continuous w.r.t input æ, then any algorithm that maps X to H is (N, Lob-robust.
Proof: It is easy to see that there exist N = [[B/A)==] disjoint n., di-diinnnio cubes, each with edge length A, satisfying that their union covers X' completely since is compact. Let Cg be one of those cubes, indexed by k. and N₂ = X' C4. We can write X' = U X4-
Consider any 8, X. If both and belong the same Xx for some k; then we have [(A(H, f(A(H, ()A(H,)),z) 2) & T.I|s - x|1b0 < LA for any algorithm A and any S E x due to the Lipschitz continuity of completing the proof.
Proof of Theorem 1 For any H. and dataset S, there exists an algorithm that maps h.
i.e. h = A(H, S). Lemma tells that Ass ([ - Lo)-robust for any À E (0, B). Theorem 9 implies I)(2,h) F(P., h)] < LA C
ym v BB=>>~ log 2 2log 5 with probability least
1 - 8, for any constants 5 E (0, 1] and E (0, B3. Since this bound holds true for any h E H. we conclude
C
sup F((P,, hi) F(P,, kEH
& LA
B \
log 2 log
m
15

---

Under review as a conference paper at ICLR 2022
The second statement is application of the first one by taking A 2 eexp(=0.5m") Indeed,
Bm a/nn and 8
sup [P(,,)) -FP(..)) & L
V
/1 A===A->x>
log 4 log
Vm
NEW
C
LBm +
[m
log 4 log 4 + m
C
LBm +
m log 4 + ma
Vm
V (1 (1+ +1g log 4)m 14 12
LBm + Cm
K (LB + 20 ng
The last inequality holds because -1 + n, proof.
a < 0 and hence nx a < 1, completing the
Rz
A.1 DEEP NEURAL NETWORKS THAT AVOID THE CURSE OF DIMENSIONALITY
Proof of Theorem 2 Denote hz(x)) x, h1(x) o (W1ho(z)) .... hx(x) o (WKhk-i(z)
By definition, the Lipschitz constant of a function g(h) is defined to be 969| Lip = sup ((V((h)),
||All251
where (B) the spectral norm of matrix B. For linear function we have || sup oWh) = [W]l.. Since o; is p;-Lipschitz for any i, we have |
(k<()))
Pk Dx|ggh--(())lla
(4)
WM
Pk (
(5)
(6)
(7)
II Pk W
(8)
K
PkSk
(9)
1=1
which proves the first statement.
Next consider a neural network A trained with Dropout (Srivastava et al. 2014). At each minibatch I of the training phase, we randomly sample thin sub-network hw, compute the gradients (z) (x) given the minibatch data, and then update each weight matrice as
w(()) : (Nor (0). where wi(") == w,((-1) -19," (1 (x)
(10)
where Normalize( (W?(") is the normalization that ||((()) || S a: < by for some tuning constant and any i, and is the learning rate.
After training (with T minibatchs), the network weights are scaled W((T) qW((T) for any where q is the drop rate. This implies that after training, we obtain a neural network hw., with all weight matrices satisfying [Willr S qb; By using the same arguments above, we have
16

---

Under review as a conference paper at ICLR 2022
(lw,a(2))llan
II
Pkl W
(11)
K
Pk WalF
(12)
k=1
Pkgba
(13)
k=1
where we have used the fact that | S ||B|| p for any B, completing the proof.
Proof of Theorem Let L be the Lipschitz constant of loss f(h, w.r. The basic property of Lipschitz functions and composition shows that L S LyLn. For any h E Har, we have Ln. S Hence L < Ljg Car I LyCasm
qK Car owing to Theorem
2
Taking x
B, Theorem
tells that
F(( bil LB+C (log 2log0)/m CLyCamm -0.5 105++CVll (log log 6)/m
sup heHar
Similar arguments can be used for family Hon, completing the proof.
A.2 CONSISTENCY PROOF
Proof of Lemma have
[F(Pa, ha) F(P2,hi))
[F(P ho) ((P,,, + F(P,,
min F(Pa, h)
min F h)
min F(P,, h)]
hch
heh
hEH
< IF(P ho) F(P,, ho)l + |(
min F(P.. h)] +
min F(Pr, h)
min F(P:
hef
hcH
keh
< |F ho) F(P,, ho)l + 6 sup heH
F(P,, F F(P,, h)l
(15)
< + 2 sup |(PP.. h) - F(P.. h)]
keM
where we have used Lemma to derive
15
from
14
B PROOFS OF THE MAIN THEOREMS FOR GANS
Proof of Corollary 3 Observe that PP,
sup DED,GEg
(VPa,, D,G)
sup E Ex-P, D(G(2)))
DED.GEg
E P. ( D(G()))) Since P_ is empirical version of P., applying Theorem will provide the generalization bounds for supnep.Ges [E 12x - D(G((2)) E. e1 (=G())))
The same arguments can be done for suppED.Ged (D V(P., P. D.G)) complet- ing the proof.
17

---

Under review as a conference paper at ICLR 2022
Proof of Theorem 6 Observe that
[V P.. D, -.
21 + (o (1 P. (D,,G,,,
(16)
< P.PP - ( - R 22
Bew BE Hu - Ri, (D((x))
Therefore
SUDDEC.DED IV P. D.G)
V P:: D.)
sup GEG.DED
Eg~P 2/ ((G(z))) Sn 1/2 D(G
sup DED
E Exn Pa 111 (D(x)) - P 111 (D(x))
(17)
P 1/ D(G(=))) 2N P. 12211 D(G(2))) z LA + Theorem I shows that sup
DED " log 2 log 6)/m, with probability at least 1 8, for any constants ó E (0, and E (0, B.]. Similarly, we have sup
C B --
P/ - E, B 1/ (D(x)) & LyLadz + GEG.DED
C -- log 2 log 62)/m, with probability at least 1 8z, for any constants 62 E (0, 1] and A E (0, B.). Combining these bounds with (17 and the union bound will lead to the first statement of the theorem.
For the second and third statements, choose À B2, B2, 8 ó.. Using the bounds for the Lipschitz constant of in Theorem 3 will complete the proof.
Proof of Theorem 7
By definition, (D: G3) = arg mingeg maxped V(Pa, D,G))
D,G) and
(D*, G*) arg minGeg maxDed ((P,, P., D,G).
Therefore
(Pa, P., G.) Pa,",,
= min max ((Pa, P., D,G) - min max V(Pa, Ps, G)G) GEG DED
(18)
GEG DED
< max max (Pa,, P., D.G) DED
max V(Pa, P,, D,G)
(19)
GEg DED
< max max GEG DED
(P,,
V(Pa P.)
(20)
< LA + C
log 2log 8) + Ly + CV ([ - X= log - 2 log 8, (2
where we have used Lemma to derive (20) from 19 and (1 from 20 The last inequality comes from Theorem completing the proof.
Lemma 3. Assume that hi and by are continuous funcction defined on compact set Z,. Then
max h (x)) max hz(z)) < max [h (x: - h2(x))
=E2.
zE2,
z6 2
min hy (x:) min
lz(z)) S max 1h (1:) - h2(2:)
xE2,
zE
Proof: Denote xi = arg max h1 (I), 2タ = arg max 2, h2(x)) It is easy to see that
h hn - h2(2z) < h (x+) h=2)²) < h1 h1 h2(xi)
Therefore
max hi (x:) - max h2(x)) = (21 - 12(25)) 5 max Ih (x) h2(x))- zEZ,
We
rewrite max (-h2(x)) & max (x)) h2(x)), completing the proof.
m (x) min h2(2))
max (-h1 (2)) +
18

---

Under review as a conference paper at ICLR 2022
C GANS AND AUTOENCODERS
C.I TIGHTNESS OF THE BOUNDS FOR GANs
Note that our bounds in Theorems 6 and in general are not tight in terms of sample complexity and dimensionality.
Taking À
Bym (/(+2)) 6
2exp(-0.5m//ot00 Ar B.m B,m-11/m=+2) 82 2 eex==exxppppeepe 2exp(=0.5mm*/tan (lmmmmmmmmm+)))))) +2) Theorem provides suppeD.Geg (VPa, Ps. D. - V(Pa, G) I (0 ((m-1/(x+)) + m m- 1m= (0(mm++)) +2) This bound
-1)
0(m-1/(n+2 + m 11/(m,, ) surpasses the previous best bound Om 1/(15m) + m 1/(1.5m.)) in
the GAN literature (Husain al. 2019).
C.2 SAMPLE-EFFICIENT BOUNDS FOR AUTOENCODERS
Husain et al. (2019) did 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 Imax ((Pa, D,G) max V(Pa, P., D,G S O(m 1/8a + m mm///)) DED
DED
where $d d' (Pa) (the 1-upper Wasserstein dimension of Pa) and 8, d'))))) We show in Appendix C.3 that 8d > 1.5ng, 8g > 1.5n even for a simple distribution, where ng is the dimen- sionality of real data, and is the dimensionality of latent codes. Therefore their bound becomes Omm 1.5mz m T.mm), which is significantly worse than our bound 0(m-1/(n+2) + m -1/mxx+ +2)). As result, our work provides tighter generalization bounds for both GANs and Autoencoder mod- els. More importantly, our results for DNNs with Dropout or spectral norm translate directly to Autoencoders, leading significant tighter bounds.
C.3 How LARGE IS 1-UPPER WASSERSTEIN DIMENSION?
This part provides example of why 1-upper Wasserstein dimension is not small. Before that we need to take the following definitions from Husain et al. (209)).
Definition (Covering number). For set C TR"" we denote (S) be the n-covering number of S, which is the smallest non-negative integer m such that there exists closed balls B1, Bz.... Bm, of radius 1 with C U Br. For any distribution P. the (dim)-ddmnnsion is (P,(PTT = inf (N) P(S) 2 1-7).
log (.(.T) log
where N,(P,T)
Definition 4 (I-upper Wasserstein dimension). The 1-upper Wasserstein dimension of distribution
P is
(r(P:= = in (2) lim simsupdee (P, =-)))==== 5
n
Consider the simple case of the unit Gaussian distribution P = Nx; 0, I) defined in the dimensional space R", We will show that the l-upper Wasserstein dimension of is d' d' Z 1.5n.
First of all, we need to see the region S such that P(S) 2 - Since P is a Gaussian, the Raymondd-Zuckrraan
Birnbaum- Raniuum--aaon----- Zuckerman inequality tells that Pr([|= 2 ny - S ,- It implies that
Pr[[]=:11 < my - 2 1) - In other words, S is the following ball:
s = fi E R": 1| < nn =
As consequence, we can lower bound the covering number of S as
Vin
N₂(S) 2
(17)
n
19

---

Under review as a conference paper at ICLR 2022
By definition we have
- :(S) 2 21 1-
(nn 1
Next observe that
1
dy (2,))=2)
=
log Ny (P,1211)=2)
(22)
log
1
n
n2
-33 + 4
log
n2
+
log "]
(23)
log !7
2
2
8 - 2
1
38
4
n
log n
(24)
2
8
2
log !]
Therefore
11 38 4
lim sup (P,171)))))
>
(25)
7-+0
2 s
The definition of (P) requires lim sup (p,7)==))))) S 8 and 8 E (2, oo). Those requirements
imply
3s-4
S and thus s 2 1 1 [ 3n + v /4+ 3n)² 32m > 3u As result, d' (P)
2
8-2
1.5n.
D WHY DOES DATA AUGMENTATION IMPOSE A LIPSCHITZ CONSTRAINT?
In this section, we study perturbed version of GANs see the implicit role of data augmentation (DA). Consider the following formulation:
min max Ex (log ((= c) + EZ~P, B. D(G(z) + c))
(26)
G D
where c ou and follows a distribution with mean 0 and covariance matrix I, a is 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 mak- ing a convolution to real and fake distributions (Roth et al.) 2017 Arjovsky Bottou (017). Let Pa)e(x) EE [p(pa( + E)], Pgre (x) = [P + e)] be the density functions of the convoluted distri- butions Pase: Pree: respectively. We rewrite V.(D, G) = Ea-P, [E, log D(x + <)] + Ez-P, [E, log(1 - D(G(z) + +)]]] Ea-Per. log D(x) + Ez-P,.. log(1 D(x)). Given fixed G. the optimal discrimina- (a)
tor is D* (x: = pa- (z))..))) according to Arjovsky & Bottou 2017 Training G is to minimize V.(D", G). By using the same argument as Goodfellow al. (014). one
that training G is equivalent to minimizing the censen-Shamme divergence d.y Patc, Pync). Appendix D.2 shows
V dist Pa) S / das(Panes Pare) + Volo)
(27)
V dis(Pat (a,, Pa.c) S v das(Pann Pgec) + vo(o)
(28)
where o(r) satisfies lim o(o) = 0. They suggest that for a fixed a, minimizing d. Pgec) a-0 implies minimizing both d Pgnc) and djs( Pg). The same behavior can be shown for many other GANs.
Lemma 4. Let Jz( be the Jacobian of f(x w.r.f its input v. Assume the functions Pa and Pg are differentiable everywhere in Z For any x E Z
( Pg (x) ( = =(p((x) - (2( + o[a)]2 + o
[TT JJ (pa) (pa)Ja(paau)
2. [pa(x) Pg (x) 2 + 2 = [Pa((x) - Pp(x)) - - O2
T Jz (Pg) (pp))
3. (r) (a).
= -[pa(x)- -p (2) to [uT JT - -p - py)u)
Lemma 5. Ifu ~ .N(0,) 7) then E., (wT AT Au] trace( AT A) = || for any given matrix A.
20

---

Under review as a conference paper at ICLR 2022
The proof of Lemma 4 appears in Appendix D.3 while Lemma 3 comes from (Avron & Toledo
2011 Hutchinson 1989). Lemmas tions.
and 5 are really helpful to interpret some nontrivial implica-
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 ( Pane), and thus also minimize d.s(Pa. Pgee) and d.ss(Paee; Pg) according to (27) and 28 Because VdJs is a proper distance, minimizing d.ss Por) leads to minimizing Ex-pa (Pa(z) Pore (3))) Combining this obser- vation with Lemma 4 we find that training G' requires both Ex [pa((r) Py (x) + o()))² and Exwpa E., Ju" J (Pg) Jz (Py)ul to be small. As a result, Exwp, [|]]]= (Pg)) should be small due to Lemma 5 A larger a encourages smaller Jacobian norm, meaning the flatter learnt distribution. A
Py(xz)
(d-e(() small o enables us to learn complex distributions. The optimal D" D*(x)) Paac()))+Pacc(0))
suggests
that a penalty on (Pg) will lead to penalty on the Jacobian of D.
is also useful to observe that adding noises to real data (x) only will require d (Pace Pg) to be small, whereas adding noises to fake data (G(z)) only will require d,s( Pgee) to be small. Lemma 4 suggests that adding noises to real data only does not make any penalty on Py. Further, noises are used for both real and fake data, we are making penalties on both J. (pt) and Jz(pa Pg)- Note that a small Jz Ps) implies Jz (pa) 전 (Pg).. As a consequence, training GAN by the loss 2 will require both the zero-order (py) and first-order (J)) informations of the fake distribution to match those of the real distribution. This is surprising. The (implicit) appearance of the first-order information of pa 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 and G. following Theorem g
Connection to data augmentation: Note that each input for D in (26 is perturbed by an e. When has a small norm, each x' = is a local neighbor of x. Noise is common way to make perturbation and can lead to stability for GANs (Arjovsky & Bottou| (017). 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 a. By this way, x' belongs to the neighborhood of x in some senses, and can be represented as x' = + for some Those observations suggest that when training D and G from a set of original and augmented images (Zhao al., 22200a b), we are working with an empirical version of (26). Note to a larger contexts than Gaussian noise, meaning that they can apply to different kinds of data augmentation.
that our proof' for inequalities (8) and Lemma
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 by Karras et al. 2020a). Lemmal Fagrees with those observations: DA for fake data only poses penalty on Jacobian of Pg only, while DA for real data only does no penalty Pg- Differrent from prior works, Lemma 4 shows that DA for both real and fake data poses a penalty on Jz (Py) and requires Jz (P₂) 8 Jz (pa). other words, DA requires the zero- and first-order informations of Pg match those of pa. while also penalizes the first-order information of the loss for better generalization of D and G. This is surprising.
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.
Appendix D
D.1 LOCAL LINEARITY
Consider function f R" I which is differentiable everywhere in its domain. f is also called locally linear everywhere. Let c = ou, where u follows a distribution with mean 0 and covariance matrix I, o 2 0, (f) be the Jacobian of w.r.t its input x. Considering +c) f(r + ou) as function of a, Taylor's theorem allows us to write f(r + =
o(a). Therefore,
E. + +c]
= [.[f()) +oJ[(f
(29)
= f(x) + o(o) o
(30)
f(x) + +((),
(31)
21

---

Under review as a conference paper at ICLR 2022
where we have used [f) 0 due to Eu[u] 0 and the independence of the elements of u. As a - O, we have [z + c)] - (x).
D.2 PROOFS FOR INEQUALITIES (5, 6)
Consider the Jensen-Shanno divergence (Paces Paec). Since vdJs proper distance, we have the following triangle inqualities:
/ dds((Pon Pa) S /ds((Pare Paoe) + v dis( (apess
(32)
V dis(Pas, Pase) S / dds((aan Paoe) + v /dddss Pa)
(33)
Next we will show that dis(Pgac gae; Pg) = o(o).
The following expression comes from a basic
property of Jensen-Shannon divergence:
P Pgre + Pg
1 (((gge)) H
dss(P gres Pg) H
(34)
where (P)) denotes the entropy of distribution
Denote ol-), 01 (-), (z)) be some functions of a satisfying lim dla) = 0. 0-0
Appendix
D.1
suggests that Poxe (x) EE, (pg = (r)) and log(p, ( (0) = (og())(r)) by using Taylor's theorem for a.. Therefore:
1 H(Pg)
/ ps(x) log (g)
(35)
2
1
1 Pgac log g =
(PP
+ oz
2
=
2
2
1
/
(grc( (z) + 02 (2(
2
/
= 2
(zd + -2(
(36)
Pare + Pg
(x) + Po(x))
Pgre(1) + +P (x(
H
log
dr
2
2
i Pane (x) + P2(
(py(x) + (a)
log
dx
2
2
{ Pane (x) + Po(x))
log
Po(x) + 50((0)
dx
2
/ Pane (a=e(x)) (x) + Po(a))
log +
2 _ dx
2
1
(Pge(()) Po (x)) log loggg(2))) (x:dd= 02(0) /
|Pgae (x) + pg(x))de
2
1
(Pgec(x) + P. P. (y
-0)(0)
1
/ Py (x) log o3(o) 2
lozg(
(37)
2
From equations 34
35
36
37
we can conclude d gees Pa) o(o). Similar arguments can be o(r). Combining those with (32) and (33) arrive
done prove d dac, Pa
22

---

Under review as a conference paper at ICLR 2022
dis(Pares Pg) S / dss(s Pore) + vo(o) dss((PaPPad 2 (dss(Parer Pave) + v v(o).
(38)
(39)
D.3 PROOF OF LEMMA 13
For any I E Z,, is worth remembering that Panc (x) = E. [p(( + e)]. Consider
Y= =Ppa - Pa(a ou) Pg()),
which is a function of u. Since u follows a distribution with mean 0 and covariance which is the identity matrix, Y is random variable. Due pa(x+e) pa(x)) toJ (pa))u+o(() from Appendix D.I we can express the variance of Y as
Var(Y)
EY²) (Y))²
(40)
By (palo + t) Pg (1)) [Bu(pa(< + 6) Pa (x))1
(41)
E, [pa(x) (p(x) o(o) oJ |pare Pa (x))2
(42)
E, (palL)) (x)) o(0))) + 20 (x(pa())) Po(x)) + o (L (pa)
T JT (Ba((p)JJ (pa) Ipan (1)
(43)
[pa(s) - Po (x) o( + B.Euulu Jz (pa) - (x))e())) - (x))
Since pz (z) does not depend on = ou, we have Var(Y) = Var(pa( + E)) = Var(pa( + ou))
which is bounded above by C'Var(ou) = Co², for some C 2 0. Combining this with (44) will result in
(x)) - P=(x)) + Co² 2 [pa(x) - (2( + o + B'E J. (2a))
(45)
completing the first statement. The second and third statements can be proven similarly.
E EVALUATION OF DATA AUGMENTATION FOR GANS
There is tradeoff in data augmentation. Making augmentation from a larger region around a given image implies 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 small region small Ø) allows the Jacobian norms to be large, meaning the learnt distributions can be complex. As a + 0, no regularization is used all.
This section will provide some empirical evidences about those analyses. We first evaluate the role of a when doing augmentation by simple techniques such 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 al. (017).
E. EXPERIMENTAL SETUPS
The architectures of G and D are specified in Figure I which follow wwn.os////aaaaana/n////// http:///wweeyyyooocoa/////aaaaaa
com/
Py We use this architecture with Spectral normalization (Miyato et al. 2018) for D in all experiments of GAN and I.SGAN. Note that, for LSGAN, we remove the last Sigmoid layer 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 (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 (00 I). We use Adam optimizer
with 3 0.5, 32 0.999. Ir 0.0002, batchsize 64.
23

---

Under review as a conference paper at ICLR 2022
Generator Network
nud1p
Batchhor tor
Vypu Newe
Leary
Lanoyfheel
LaaioyFuuu Fua.l
Linesr
Linkai
BaishNor
Liwer
Lineer
Fake Image
Disctminator Network
Fake Image
Flaten
Lindar
Liveer
Leoryfouu
Linder
Signod
Figure 1: The architectures of G and D with the negative slope of LeakyRuLU is 0.2
GAN [aaaaz
GAN - |aD/ax
LSGAN paWaaz|lr
LSGAN |aD/ax
0.75
JaV/aze
JaVizz
9.5
Epoch
Epoch
poch
Epoch
7
6667
24
Figure 2: Some behaviors of GAN (first two subfigures) and LSGAN (last two subfigures) with different for augmentation. Both aD and 8V denotes the Frobenious norm.
measured along the training process. || !|
E.2 THE ROLE OF FOR DATA AUGMENTATION
In this experiment, the input of D which includes real and fake images are augmented using transla- tion. The shifts in horizontal and vertical axis sampled from discrete uniform distribution within interval [-s, s). where = 2 corresponds to /2, corresponds to V6.67, and corresponds to V24.
Jacobian norms of 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 G. need fix D when training G. Therefore we did the following steps: (i) train both G and for 100 epochs, (ii) then keeping D fixed, we further train G to measure its Jacobian norm along the training progress. We chose [v6.67, V4, 24 and augmented 64, 96, 128 times for each image respectively.
Figure 3 shows the results. We observe that a higher a provides smaller Jacobian norm G. Interestingly, the norm decreases training G more, suggesting that G gets simpler.
24

---

Under review as a conference paper at ICLR 2022
GAN ||G/az]|
LSGAN |aG/az||
|aG/azll
|aG|ozil
22-
18-
250
500
750
25
500 Minibatch
753
Minibatch
0= 66.67
o=
V14
0=
Figure 3: Some behaviors of GAN and LSGAN with different for augmentation. aG 0z
is measured
along the training process.
GAN [[aVazz]
GAN |aD]ax]
LSGAN JaWazz|r
LSGAN |
JaDiaxi
IDDiOXI
0.35
36%
0.00
Epoch
Epoch
Epoch
Epoch
0.01
0.1
0.5
Figure 4: Some behaviors of GAN (first two subfigures) and LSGAN (last two subfigures) when augmenting images by adding noises. Both aD and Øv are measured along the training process. Hi 82
E.3 AUGMENTATION BY ADDING NOISES
In this experiment, the input of D which includes real and fake images augmented by adding Gaussian noise (0, o). We choose a E {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. can be seen from the figure that the higher a provides smaller Jacobian norms. This 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 aG/0z is. We choose behaviour can be observed. Larger a often leads to smaller norms. It is worth noting that the Jacobian norm will be zero as a too large. In this case both D and may be over-penalized. Those empirical results support well our theory.
{0.5, 2, Figure show the results. The same
F EVALUATION OF SPECTRAL NORMALIZATION
This section presents an evaluation on the effect of Lipschitz constraint by using spectral normal- ization (SN) (Miyato et al. 2018). We use Saturating GAN and LSGAN with four scenerios: penalty: SN for G only; SN for D only; SN for both and G. The setting for our experiments appears in subsection E.1
The results appear 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 reach optimality. When SN is used
25

---

Under review as a conference paper at ICLR 2022
GAN ||a/az||
LSGAN ||a/az|
|aG/azll
|aG/azla>
#2-
250
300
750
250
300 Minibatch
750
Min blnhhbatch
0.5
0
aG Figure 5: Some behaviors of GAN and LSGAN when augmenting images by adding noises. measured along the training process.
is
0s
Epoch
penatty
Peratty
Penalty
Peralty G&D
Epach
Epoch
Epoch
Epoch
penalty
Peralty
Penalty
Peralty G&D
Figure 6: Some behaviors of Saturating GAN (top row) and LSGAN (bottom row) in different situations. V, is the loss for training the generator, and FID measures the quality of generated images, the lower the better.
for G, it seems that G has been over-penalized since the gradient norms almost zero, meaning that G may be underfitting. This behavior appears in both GAN and LSGAN, and was also observed before (Brock al.] 2019). The most sucessful case the use of SN for 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 | /02l/ of the generator are stable and belong to small domains, suggesting that the use of SN for D can help us penalize the zero- and first-order informations of the loss.
Our experiments suggest three messages which agree well with our theory in Theorem X Firstly, when no penalty is used, the Lipschitz constant of a hypothesis may be large in order to well fit the training data. this case the generalization may not be good. Secondly, we can get stuck at underfitting if penalty Lipschitzness is overused. The reason is that heavy penalty can result in a small Lipschitz constant (thus simpler hypothesis), meanwhile a too simple hypothesis may cause 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 better generalization.
26

---

Under review as a conference paper at ICLR 2022
G FURTHER DISCUSSION
We have discussed both generalization and consistency Section 3] We next provide some inter- pretations from our theoretical results which may be helpful in practice.
We may want find an unknown (measurable) function n7()) based on training set S of size m A popular way is to select a family H. (e.g., an NN architecture) and then do training on to obtain a specific hn H. The quality of h, can be seen from different levels (Bousquet et al. 2004):
F1. Optimization error: erro(ho: k(,)) F(P,, h1) - F(P,, hmm) for comparing with
hm = arg mi F(Pa, h) which is the best in for the training data;
E2. Generalization gap: errg(ho) = [F(P,, ho) - F(P2. ho)l to see the difference be-
tween the empirical and expected losses of ho:
E3. Consistency rate: erro )- F(2,, ho) - F h()) for comparing with the best function h- arg minMER F(P,, h) in Hi;
E4- Bayes gap: grrg 1)) F(P.: hb) F(P.. 11) for comparing with the truth.
A small optimization eπror may not always lead to good generalization.
A small generalization gap is insufficient to explain a high success in practice. Indeed, (rrg(ha) can be small although both empirical and expected losses are high. The of this quantity poses long debate (Nagarajan & Kolter 2019 Negrea et al., 2020).
From Theorem ! one may try to penalize the Lipschitz constant of the loss as small as pos- sible to ensure small generalization gap. However, as explained before, such naive appli- cation may not lead to good performance. The reason is that family H may he much smaller and the members of H. will have lower capacity L. decreases. Note that large decrease of capacity easily leads to underfitting, and hence F(Pa, ho) will be high. Our experiments in Appendix P provide further evidence when spectral normalization is overused.
Those observations suggest that making only optimization generalization gap small is not enough. Both should be small, and so is consistency rate due to Lemma
When does small consistency rate still lead to bad generalization? In those bad cases, the Bayes gap errb(h,, 71) will be large. Note that BTTB(ho, 7) err.(h., h²) + erra err,(H), where err,(H) F(P,. 2 hi*) P(P... -) is often known as the approximation error and measures how well can functions in 7/ approach the target (Bousquet al. 2004). There- fore erra (?L) represents the capacity of family H. A stronger family with higher members will lead to smaller F(P,, h²) and hence smaller erra erra(H). Those observations imply that, provided loss f is not a constant function, a bad generalization with small consistency rate happens only when H. has low capacity.
When working with high-capacity family H. small consistency rate is sufficient to ensure good generalization. Lemma | suggests that it is sufficient to ensure good generalization by making both optimization error and generalization gap 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.
For simplicity, we limit the discussion measurable functions.
27


Reviews:
[{"review_id": "sDbEmhlI-HQ", "reviewer": "Reviewer_wjLb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Writing in the abstract and introduction:**\n\nThe introduction and abstract are not written well and need several revisions before the paper is fit for publication. This is one of the biggest weaknesses of the paper. I will provide three examples here of areas of improvement. Specifically, the introduction does not do the paper justice and can easily turn off a reader before they even get to the bulk of the work (which is interesting and has value). \n1) The whole abstract is very vague and doesn’t explain much. The first sentence is not saying almost anything at all and the last sentence mentions “the long mystery of why imposing a Lipschitz constraint can help GANs to generalize well in practice” offhandedly. The last sentence was actually very confusing to me at first because plenty of work discusses Lipschitz constraints on GANs, so initially I thought that the authors were not aware of these (not-so-obscure) papers. However, after reading the related works I understood that the authors meant something more like “although experimentally Lipschitz constraints have been used with great success, the relationship between imposing a Lipschitz constraint and GAN generalization is not theoretically understood”. Whatever the authors choose to say, it should be really clear what they mean, ESPECIALLY in the abstract and introduction. \n2) There are also several typos and things that are worded strangely. For example, in the second paragraph it is written “... two players competing each other.” This should be “... competing against each other.” \n3) The introduction does very little to explain the actual problem in the context of literature. The authors say that “little has been known about the generalization of the trained players” and “The standard learning theories still lack an efficient tool to analyze GANs”. These are too vague for a reader to understand what THIS paper is addressing specifically. \n\n**Specificity and confusing things:**\n\nThe authors lack specificity in several areas. Without being specific, the paper is confusing and the reader must guess what is going on. I will provide three examples here of the lack of specificity. The following are all weaknesses:\n\n1) In the abstract itself, the authors say that GANs are “complex” in their first sentence. This is true in many ways so it is unclear how the authors address this. They say that they use efficient tools, but what does efficiency even mean here? In other words, in the abstract it isn’t clear how the work done is addressing actual open problems because of a lack of specificity. \n2) In the first paragraph of the paper, they introduce the latent distribution z. In section 3, they call the data distribution (as far as I can tell) z, which is confusing. If they want to use z to represent both the latent variable and the data, then they should explicitly say that they are switching notation, although they should just stick to one.\n3) The theorems and lemmas are labeled together; for example, Theorem 1, Theorem 2, Theorem 3, Lemma 4, then Theorem 5 without having Lemmas 1-3 and 5 and not having Theorem 4. However, the corollaries have independent numbering, which is confusing when trying to find things. Stick to one convention.\n\n**Theorem 1:**\n\nMany of the assumptions are valid, which is a big strength. For example, it is reasonable that Z is bounded by B as image datasets typically lie in the hypercube.\nHowever a few of the assumptions are not representative for GANs in practice, which is a weakness. It doesn’t seem reasonable that the loss is bounded, as most losses are not. The typical GAN loss stated in this paper is not bounded and hence Theorem 1 does not apply. The Wasserstein loss and f-divergences in general need not be bounded. So, the authors need to justify this hypothesis. \nRegardless, this result is very interesting and a great contribution (strength). The result that you can generalize better with simpler functions seems to go against the intuition that a highly complex hypothesis class is beneficial. Although this raises the important question… Since the generalization error is based on the loss f (and F), are we just generalizing better because we are making BOTH $F(P_z, h)$ and $F(\\hat P_z, h)$ less able to distinguish differences? For example, clearly if we choose f = 0 then it is 0-Lipschitz and we get “perfect generalization” but obviously this isn’t good. This is a weakness until it is explained.\n\n**Theorem 2 and 3:**\n\nTheorem 3 is great and reasonable (strength). The authors do a great job showing how dropout and spectral normalization can be used to get better generalization bounds. It seems to me that Theorem 2 might be better renamed as a proposition because it isn’t central and not very hard to prove. But that’s just my opinion.\n\n**Section 3.2:**\n\nIn Theorem 5 and Corollary 1, it is not clear that these models are consistent, which is a weakness. This needs to be cleared up because that is the claim of this section. Obviously as $m \\rightarrow \\infty$ we have that $2(LB + 2C)m^{−\\alpha/n} \\rightarrow 0$ but we don’t know if $\\epsilon_0 \\rightarrow 0$. Of course, the authors have this as a condition in Corollary 1, but when this condition is met is not known as far as I can tell. Because of this, one cannot conclude that the models are consistent. The authors mention that sometimes $\\epsilon_0 = 0$ but this just shows that $\\epsilon_0 = 0$ is attainable.\n\n**Section 4.1:**\n\nThe authors state “Theorem 7 also suggests that penalizing the zero-order (C) and first-order (L) informations of the loss can improve the generalization.” This is true but it begs the question, as I mentioned above, of why? More specifically, if L becomes 0, then the loss becomes meaningless. In this case, we have that we generalize perfectly but it is not interesting. If C is decrease, why does this matter? If it is just an upper bound on the loss (as mentioned on assumption 1) then this is interesting but not intuitive. However, if the whole loss is bounded as explained in the second paragraph of Section 3, then it is clear why generalization is good, because with C = 0, the loss will always be zero and hence we generalize perfectly again but the problem is not interesting. The authors need to address these core ideas and hence this is a weakness.\n\n**Note on theory:**\n\nOverall the theory seems very thorough and correct, although I did not go through the proofs. For this reason, this is a strength, a really big one. The authors do a great job on the actual theory and I did not find a problem with it. Most of the paper’s weaknesses which I state above are with the writing or the interpretation of the results.", "summary_of_the_paper": "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.", "summary_of_the_review": "Please provide a short summary justifying your recommendation of the paper.\n\n**Strengths:**\n\n1) The math is solid and seems well developed.\n2) The results are interesting as they tie generalization to Lipschitz continuity.\n\n**Weaknesses:**\n\n1) The abstract and introduction are poorly written\n2) The implications of the mathematical results have serious potential logical problems. I asked the authors to clarify in case there is some confusion. However, as it stands, it seems to me that their limiting-Lipschitzness idea does not actually reflect good generalization in practice, which is what they claim. This is because in their framework, one can use the 0 function for generator and loss and “generalize perfectly” although this is not intuitively what we want.\n3) The consistency results are also questionable because they have a hypothesis in the theorems that is almost as strong as the result, which causes an almost circular reasoning. To be blunt, the actual logic is correct, but their result is very weak given this hypothesis.\n\nIf the authors had addressed these two weaknesses, I would have given them an 8 since this paper is solid otherwise.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "R3kjDMzCR6l", "reviewer": "Reviewer_wKt9", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Generative adversarial networks (GANs) usually achieve satisfactory generalization performance in practice, although their optimization problems are solved over deep neural network models with large capacities. This paper attempts to understand how the generalization error will depend on the Lipschitz constant of the neural networks in GANs. To reach this goal, the paper shows Theorem 1 bounding the generalization error with the Lipschitz constant of the neural network function (L) and the diameter of the learned variables B. Then, the paper applies this result to the GAN problem and connects the assumption on the Lipschitz constant to spectral normalization and dropout regularization techniques.\n\nThe paper studies a highly interesting theoretical problem to understand the success of Lipschitz regularization methods. However, I think the shown bounds are too conservative and do not justify the generalization success in GANs. This is because the generalization result in Theorem 1 aims to bound the generalization error uniformly over the entire space of 1-Lipschitz functions. Consequently, the bounds are all exponentially growing with the dimension of data vector (n) and become vacuous for moderately high-dimensional data vectors with a dimension greater than 20 or so. Therefore, the bounds do not address the curse of dimensionality in deep learning experiments and only show the generalization error is bounded with an exponential function of dimension n which does not apply to practical deep learning settings.  On the other hand, the generalization bound in (Arora et al 2017) does not exponentially grow with data dimension through bounding the number of variables of the neural net players as a specification for the GAN problem.  Also, the paper does not provide any numerical evaluation of the shown bounds and how they change with the actual generalization error in GANs. Due to these reasons, I do not recommend this paper for publication in its current form. The paper's generalization bounds can be significantly improved by taking the optimization algorithm and the design of neural network players into account, and I suggest the authors improve their results in that way.  ", "summary_of_the_paper": "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. ", "summary_of_the_review": "While the paper proves several generalization bounds, its main result (Theorem 1) models a neural network by only its Lipschitz constant and tries to bound the generalization error uniformly over all 1-Lipschitz functions. Therefore, the bounds grow exponentially with the data dimension and lose their power for even moderately large data vectors including all practical deep learning settings. Therefore, I think the paper's analysis does not help with understanding generalization in GANs and needs to be significantly improved by considering the design of neural net players and the optimization algorithm.   ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "BOZbO6X0xFe", "reviewer": "Reviewer_NvVe", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very interesting and pretty much self-contained. It is fairly organized and connected to previous theoretical and empirical findings in the community (good related work). The background required to understand the details is provided and some quite interesting theorems are discussed and proven.  \nA few minor issues can be improved to make it easier to understand some sections and claims of the paper.\n \n* in the abstract \"..our bounds show that penalizing the zero- and first-order informations of the GAN loss will...\" it might not be clear yet what zero or first-order information means.\n\n* notation of Z used both for data and noise in GAN isn't a good choice.\n\n* output of D to be in [α, β] ⊂ (0, 1) as suggested by Salimans et al. (2016). While I agree with the authors that many implementations of saturating GANs do so (e.g. α = 0.1 β=0.9), to the best of my knowledge. Salimans et al only set  β < 1 but keep α at 0. \n\n* page 9, first line:  \"one player (D or G) only can help, but maybe not enough\" remove \"only\"?\n\n* page 15, Definition 2: I think \\bf{S} is a subset of Z^m (not an element) and ε(·) is from the power set of Z^m to R? \n", "summary_of_the_paper": "This paper's primary focus is to provide insights into the relation between Lipschitz-continuity and the generalization of DNNs. \nCompared 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. ", "summary_of_the_review": "I find the paper's findings quite interesting and to be the best of my verification correct.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "AwUoiunh0c-", "reviewer": "Reviewer_yK3Y", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In this work, the authors provide the generalization and consistency of Lipschitz neural networks (NNs) with spectral normalization and dropout. Consistency is basically the difference between the objectives achieved at the optimal solution and a computed solution. In order to get a meaningful generalization bound, previous results require the number of layers to be linear to the number of samples in the worse case, whereas the authors reduce the number of layers to be logarithmic in the sample size. Furthermore, the authors derived the Lipschitz-based generalization bounds for GANs, showing that imposing zero-order and first-order constraints on GAN loss could improve GAN generalization. \n\nOverall I think this is a work with very interesting theoretical results. The theoretical results are novel and the analysis seems to be solid. I have the following questions:\n\n1. What does \"curse of dimensionality\" mean in this paper? When talking about the \"curse of dimensionality\", I thought that the dimensionality of each data sample is high, but it seems that the \"curse of dimensionality\" means something else in this paper. Is it the number of neural network layers?\n\n2. In Theorem 1, 1 there is a $\\lambda$ which is multiplied on $L$. Does that mean you can set an arbitrarily small $\\lambda$ such that you do not need the Lipschitz continuity to ensure a function to generalize? \n\n3. $q$ in Theorem 2 and 3 are re-used. $q$ appears in Theorem 3, 1 SN-DNNs and 2 Dropout DNNs, but have different meanings. In one line below Dropout DNNs in Theorem 3, there is one sentence “If the number of layers $K \\ge -\\frac{1}{2} \\log_q m$”, which $q$ is this?\n\n4. I understand in Theorem 1 that a smaller Lipschitz constant $L$ could lead to better generalization performance. But I’m also wondering, could a smaller $L$ also induce a higher  $F(P_z, h^*)$ value in Theorem 5 and 6? Does that mean adding the Lipschitz constraint to NNs is bad, i.e., reducing the network capacity such that the error is always high? Similarly, in Sec. 4, could a smaller $L_g$ for the generator reduce the power of the generator to model the real data distribution? \n\n5. The bound in Theorem 8 is loose. Did the authors tighten the bound using spectral norm or Dropout? \n\n6. The authors analyze the effectiveness of using Lipschitz constraints in GANs from the generalization perspective. But I don’t think simply from the generalization error is sufficient to explain the effectiveness of imposing Lipschitz constraints. I think Lipschitz constraints could make the optimization of GANs easier, preventing the gradient from vanishing and exploding, as analyzed in the WGAN-GP paper. \n", "summary_of_the_paper": "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\nis logarithmic in sample size. Furthermore, the generalization of a GAN, whose discriminator and generator are both Lipschitz continuous, is given. \n", "summary_of_the_review": "The theoretical results are novel and solid to me. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to analyze the generalization error of deep learning models and GANs using the Lipschitz coefficient of the model.

There was significant discrepancies in the evaluation of the paper among reviewers. While all reviewers acknowledged the interesting theoretical approach to understand generalization and the relevance to ICLR of the problem, they disagreed about the readiness level of the paper. Some concerns were expressed in terms of clarity (and the AC agrees with these), but most importantly, reviewer wKt9 pointed an important flaw in the current analysis that was not properly responded to by the reviewers (see below). In discussion, other reviewers were also concerned by this flaw, and so the AC decided to recommend a major revision of the paper taking the reviewers comments in consideration.

## Important flaw in the paper analysis (from wKt9)

Basically, Theorem 1 assumes that a loss $f(h,x)$ is $L$-Lipschitz w.r.t. input $x$ in some compact set of diameter $B$ for any $h$. The author shows that the:
$\sup_{h \in H} |E_{P} f(h,X) - E_{\hat{P}} f(h,X)|$ is upper-bounded by $L B + C \sqrt{\text{stuff}/m}$.

The concern of wKt9 is that the LHS is upper-bounded *trivially* and deterministically by the tighter $L B$ [see proof sketch next] for any distribution $P$ and $\hat{P}$ just because of the compactness of the input set and that $f$ is $L$-Lipschitz; one does not even need to include the number of samples $m$ in the analysis (thanks to the very strong assumption on $f$). The reviewer also was concerned that later (Theorem 3), the authors study ways that we can make $L$ exponentially small (which is interesting), but this has both the issues that:
1) it tells you nothing about the absolute performance of your network, as this only bounds the variation between any two distributions (indeed including the empirical and true distribution; but the fact that it also contains all distributions should indicate how loose this bound is!), and so perhaps the best empirical error one can obtained is still big
2) the current version of Theorem 3 uses a loose bound with a dependence on $m$ which was not even needed (as per the result above).

While it's true that empirically one can observe small empirical error, and thus combining this with a small Lipschitz constant would indicate good absolute performance; but the current presentation of the theory is rendered quite problematic by the above refinement, and should be corrected in a revision.

### Proof sketch:
For simplicity, I'll prove it for $P$ being a discrete distribution and $\hat{P}$ being the empirical; but I'm pretty sure you can extend it to continuous distributions as well.

Note that we have $|f(h,x) - f(h,x')| \leq L B$ for all $x, x'$ in the compact set of diameter $B$ and for all $h$.

Now $$E_{P} f(h,X) - E_{\hat{P}} f(h,X) = \sum_j \pi_j f(h, x_j') - \frac{1}{m} \sum_i f(h,x_i)$$

For each $x_i$, associate several $x_j$'s so that the total sum of their probabilities is $1/m$ (split some $\pi_j$ in multiple pieces if necessary) -- we can augment the index set for these new pieces, to obtain new probabilities $\pi_j'$ and call $I_i$ the set of associated indices to $x_i$. We have $\sum_{j \in I_i} \pi'_j = 1/m$

We thus have:
$$E_{P} f(h,X) - E_{\hat{P}} f(h,X) = \sum_i \sum_{j \in I_i} \pi'_j \left[ f(h, x'_j) - f(h,x_i) \right]$$

Thus:
$$|E_{P} f(h,X) - E_{\hat{P}} f(h,X)| \leq  \sum_i \sum_{j \in I_i} \pi'_j \left| f(h, x'_j) - f(h,x_i) \right| \leq L B$$

This is true for any $h$, so this is also true for the $\sup$, *deterministically*! QED
Decision: Reject