Smoothness and Stability in GANs
Authors: Casey Chu
Kentaro Minami
Kenji Fukumizu
Venue:  (2020)
Keywords: generative adversarial networks
stability
smoothness
convex conjugate

Abstract: Generative adversarial networks, or GANs, commonly display unstable behavior during training. In this work, we develop a principled theoretical framework for understanding the stability of various types of GANs. In particular, we derive conditions that guarantee eventual stationarity of the generator when it is trained with gradient descent, conditions that must be satisfied by the divergence that is minimized by the GAN and the generator's architecture. We find that existing GAN variants satisfy some, but not all, of these conditions. Using tools from convex analysis, optimal transport, and reproducing kernels, we construct a GAN that fulfills these conditions simultaneously. In the process, we explain and clarify the need for various existing GAN stabilization techniques, including Lipschitz constraints, gradient penalties, and smooth activation functions.

Published as a conference paper at ICLR 2020
SMOOTHNESS AND STABILITY IN GANS
Casey Chu
Kentaro Minami
Stanford University
Preferred Networks, Inc. minami @preferred. ip
Kenji Fukumizu
The Institute of Statistical Mathematics Preferred Networks, Inc. fukumi zuê sm.
ac. acc.ac....
ABSTRACT
Generative adversarial networks, or GANs, commonly display unstable behavior during training. In this work, we develop principled theoretical framework for understanding the stability various types of GANs. In particular, we derive conditions that guarantee eventual stationarity of the generator when it is trained with gradient descent, conditions that must be satisfied by the divergence that is minimized by the GAN and the generator's architecture. We find that existing GAN variants satisfy some, but not all, of these conditions. Using tools from convex analysis, optimal transport, and reproducing kernels, we construct GAN that fulfills these conditions simultaneously. In the process, we explain and clarify the need for various existing GAN stabilization techniques, including Lipschitz constraints, gradient penalties, and smooth activation functions.
INTRODUCTION: TAMING INSTABILITY WITH SMOOTHNESS
Generative adversarial networks (Gooffelow et al. 2014), or GANs, are powerful class gen- erative models defined through minimax game. GANs and their variants have shown impressive performance in synthesizing various types of datasets, especially natural images. Despite these suc- cesses, the training of GANs remains quite unstable in nature, and this instability remains difficult to understand theoretically.
Since the introduction of GANs, there have been many techniques proposed stabilize GANs training, including studies of new generator/discrinnnato architectures, loss functions, and regular- ization techniques. Notably, (rrjossyy et al. (2017) proposed Wasserstein GAN (WGAN), which in principle avoids instability caused by mismatched generator and data distribution supports. In practice, this is enforced by Lipschitz constraints, which in turn motivated developments like gradi- ent penalties (Gulrajani et al. (017) and spectral normalization (Miyato et al., 2018). Indeed, these stabilization techniques have proven essential achieving the latest state-of th--hh--rttttttt results (Karras et al. 2018 Brock et al.] 2019).
On the other hand, solid theoretical understanding of training stability has not been established. Several empirical observations point to incomplete understanding. For example, why does apply- ing gradient penalty together spectral norm seem to improve performance (Miyato et al.) 2018), though in principle they serve the same purpose? Why does applying only spectral normal- ization with the Wasserstein loss fail (Miyato 2018), even though the analysis Arjovsky et al. (017) suggests it should be sufficient? Why applying gradient penalties effective, even outside their original context the Wasserstein GAN (Fedus et al. 2018)
In this work, we develop framework analyze the stability of GAN training that resolves these apparent contradictions and clarifies the roles of these regularization techniques. Our approach con- siders the smoothness of the loss function used. In optimization, smoothness is well-known dition that ensures that gradient descent and its variants become stable (see e.g., [Bertsekas] (1999)) For example, the following well-known proposition is the starting point of our stability analysis: Proposition (Bertsekas (1999). Proposition 1.2.3). Suppose f Rp - is L-smooth and bounded below: Let Tk-1 Ts [z(x) Then [[V](xx)] 0 as k

---

Published as a conference paper at ICLR 2020
This proposition says that under smoothness condition the function, gradient descent with constant step size 7. approaches stationarity (i.e., the gradient norm approaches zero). This is a rather weak notion of convergence, it does not guarantee that the iterates converge to a point, and even if the iterates do converge, the limit is a stationary point and not necessarily an minimizer.
Nevertheless, empirically, not even this stationarity is satisfied by GANs, which are known fre- quently destabilize and diverge during training. To diagnose this instability, we consider the smooth- ness of the GAN's loss function. GANs are typically framed minimax problems of the form inf sup I (10;
8
where I is a loss function that takes a generator distribution and discriminator and 0 E R denotes the parameters of the generator. Unfortunately, the minimax nature of this problem makes stability and convergence difficult to analyze. To make the analysis more tractable, we define J(H) = sup, I (n, :p), that (I) becomes simply
inf (uo).
(2)
This choice corresponds to the common assumption that the discriminator is allowed reach opti- mality at every training step. Now, the GAN algorithm can be regarded as simply gradient descent on the R" if this function + J (ue) satisfies the smoothness assumption, then the GAN training should be stable in that it should approach stationarity under the assumption of an optimal discriminator.
function 0 + ((ua), which may be analyzed using Proposition
In particular,
In the remainder of this paper, we investigate whether the smoothness assumption is satisfied for various GAN losses. Our analysis answers two questions:
Q1. Which existing GAN losses, any, satisfy the smoothness condition in Proposition I
Q2. Are there choices of loss, regularization, or architecture that enforce smoothness in GANs?
As results of our analysis, our contributions are as follows:
1. We derive sufficient conditions for the GAN algorithm be stationary under certain sumptions (Theorem D] Our conditions relate to the smoothness of GAN loss used as well as the parameterization of the generator.
2. We show that most common GAN losses do not satisfy the all of the smoothness conditions, thereby corroborating their empirical instability.
3. We develop regularization techniques that enforce the smoothness conditions. These reg- ularizers recover common GAN stabilization techniques such as gradient penalties and spectral normalization, thereby placing their use firmer theoretical foundation.
4. Our analysis provides several practical insights, suggesting for example the use of smooth activation functions, simultaneous spectral normalization and gradient penalties, and a par- ticular learning rate for the generator.
1.1 RELATED WORK
Divergence minimization Our analysis regards the GAN algorithm as minimizing a divergence between the current generator distribution and the desired data distribution, under the assumption of an optimal discriminator at every training step. This perspective originates from the earliest GAN paper, in which Goodfellow et al. (2014) show that the original minimax GAN implicitly mini- mizes the Jensen-Shannon divergence. Since then, the community has introduced large number of GAN or GAN-like variants that learn generative models by implicitly minimizing various di- vergences, including f-divergences (Nowozin et al. (2016). Wasserstein distance (Arjovsky et al.) 2017], and maximum-meat discrepancy (Li al. Unterthhnrr al. 2018). Meanwhile, the non-saturating GAN (Goodfellow et al.) 2014) has been shown to minimize a certain Kullback- Leibler divergence (Arjovsky & Bottou| 2017). Several more theoretical works consider the topo- logical, geometric, and convexity properties of divergence minimization (Arjovsky & Bottou| 2017 al. 2017 Bottou et al. 2018 Farnia & Tse 2018 Chu et al. 2019). perspectives that we draw heavily upon. Sanjabi et al. (2018) also prove smoothness of GAN losses in the specific case of the regularized optimal transport loss. Their assumption for smoothness is entangled in that it involves a composite condition on generators and discrininators, while analysis addresses them separately.
2

---

Published as a conference paper at ICLR 2020
Table I: Common GANs, their corresponding loss functions, and their optimal discriminators.
Loss function J(H)
Optimal discriminator (x(x))
Minimax GAN
Das(H ll (O)
log
(4(2))
2
(oz)+
Non-saturating GAN
D + 2 10)
2
1 log ((=))+ol=)))
Mo(a)
Wasserstein GAN
Wi(a, mo)
arg max JeLip, E Bymeel [f()] - E By [f(v]]
GMMN, Coulomb GAN
MMD (H, IPM=(u,,o)
E Byny K (x, u)1 - By [xx y)
IPM-GAN
arg max SEF Bynn [J()) Ey-nu [sr)]
Other approaches Even though many analyses, including ours, operate under the assumption of an optimal discriminator, this assumption is unrealistic in practice. Li et al. (2017b) contrast this optimal discriminator dynamics with first-order dynamics, which assumes that the generator and discriminator use alternating gradient updates and is what is used computationally. As this is differing approach from ours, We only briefly mention some results this area, which typically rely on game-theoretic notions (Kodali al. [017 Grnarova al.. 2018 Oliehoek al. (018) or local analysis (Nagarajan & Kolter 2017: Mescheder et al.) 2018). 1) Some of these results rely on continuous dynamics approximations of gradient updates; contrast, our work focuses on discrete dynamics.
1.2 NOTATION
Let IR = IR U f00.-00), We let P(X) denote the set of all probability measures on compact set X C Rd. We let (X and C(X) denote the dual pair consisting of the set of all finite signed
measures on X and the set of all continuous functions X + RR For any statement we let x {A] be if A is true and oo if A is false. For Euclidean vector its Euclidean norm is denoted by || and the operator norm a matrix
denoted by ||A i.e.. ||A||2 = sup] || | A
function f X + between two metric spaces is a Lipschiit if dy f (222)= S adx (#1, x2). A function f IRd I is 3-smooth if its gradients are 3-Lipschitz, that is, for all x2 E R
[[V - V)(y) 12 I B| x vll2.
SMOOTHNESS OF GAN LOSSES
This section presents Theorem 1
which provides concise criteria for the smoothness of GAN losses.
In order to keep our analysis agnostic to the particular GAN used, let J P(X) - R. be an arbitrary convex loss function, which takes distribution over X C Rd and outputs real number. Note that the typical minimax formulation of GANs can be recovered from just the loss function using convex duality. In particular, recall that the convex conjugate J C(X) - R of J satisfies the following remarkable duality, known as the Fenchel-Morent theorem:
(+()):= == s / ((x) du 1(4),
((n) sup / (p (p)). pEc(X)
(3)
Based on this duality, minimizing J can be framed as the minimax problem
inf J(p) = inf sup / p(x)) du (T) == (EP(X)
inf sup
s),
(4)
REP(X) pec())
MEP(X) MEP(X) pec(x)
recovering the well-known adversarial formulation of GANs. We now define the notion of an opti- mal discriminator for an arbitrary loss function J, based on this convex duality:
Definition (Optimal discriminator). Lei J : MM() ) - IR be a convex, ls..c, proper function. An optimal discriminator for probability distribution μ E P(X) is continuous functioo D X - I. that attains the maximum of the second equation in 3 i.e.. (p) = [ du J (
This definition recovers the optimal discriminators of many existing GAN and GAN-like algorithms (Farnia & Tse. 2018 Chu et al. 2019). most notably those in Table Our analysis will apply to any algorithm in this family of algorithms. See Appendix B for details this perspective.
3

---

/ Published as a conference paper at ICLR 2020
We also formalize the notion of family of generators:
Definition 2 (Family of generators), A family of generators is set of pushforward probability measures {ue Joy w E R,), where w is a fixed probability distribution on (the latent variable) and fe Z X is measurable function (the generator).
Now, in light of Proposition [ we are interested in the smoothness of the mapping 0 + J ( ) which would guarantee the stationarity of gradient descent on this objective, which turn implies stationarity of the GAN algorithm under the assumption of an optimal discriminator. The following theorem is our central result, which decomposes the smoothness optimal discriminators and the family of generators.
+ J(ua) into conditions on
Theorem 1 (Smoothness decomposition for GANs). Let J M(X) + T. be a convex function whose optimal discriminators D2 + satisfy the following regularity conditions:
(D1) x + p (x) is a-Lipschitz
(D2) x + V 2 (z) -1-Lipschitz
(D3) jr + V u (x) ) is f2-Lippchitz w.r. the 1-Wasserstein distance.
Also, let μig Jeww be a family of generators that satisfies:
(G1) 0 + fz( is A-Lipschitz in expectation for z w. i.e, Eewwllife ffz (z)]lel s 1 - 02112, and
(G2) 0 D2fo(2) is B-Lisshhitzz in expectation for w. ie., Exow D1, Bl fo, (2)
S B100, 02l12.
Then + ((a) is T-smooth, with I. = aB + A2 + (2).
Theorem D connects the smoothness properties of the loss function J/ with the smoothness properties of the optimal discriminator 2,,, and once paired with Proposition]] [ it suggests a quantitative value I for a stable generator learning rate. In order to obtain claims of stability for practically sized learning rates, is important tightly bound the relevant constants.
In Sections 4 to 6. we carefully analyze which GAN losses satisfy (DI). (D2), and (D3), and with what constants. We summarize our results in Table 2 it turns that none of the listed losses, except for one, satisfy (D1), (D2), and (D3) simultaneously with finite constant. The MMD-based loss satisfies the three conditions, but its constant for (DI) grows as unfavorable dependence on the data dimension d that forces an unacceptably small learning rate. See for complete details of each condition. This failure of existing GANs to satisfy the stationarity conditions corroborates the observed instability of GANs.
O(vd), which is an
Table 2: Regularity of common GAN losses.
(D1)
(D2)
(D3)
Minimax GAN
X
X
X
Non-saturating GAN
X
X
X
Wasserstein GAN
V
X
?
IPMs
X
V
?
2MD
/
Theorem I decomposes smoothness into conditions on the generator and conditions on the dis- criminator, allowing clean separation of concerns. In this paper, we focus the discriminator conditions (DI), (D2), and (D3) and only provide an extremely simple example of a generator that satisfies (GI) and (G2), in Section 7 Because analysis of the generator conditions may become quite complicated and will vary with the choice of architecture considered (feedforward, convolutional, ResNet, etc.), leave detailed analysis of the generator conditions (GI) and (G2) as promising avenue for future work. Indeed, such analyses may lead to new generator architectures or generator regularization techniques that stabilize GAN training.
4

---

Published as a conference paper at ICLR 2020
3 ENFORCING SMOOTHNESS WITH INF-CONVOLUTIONS
In this section, we present a generic regularization technique that imposes the three conditions suf- ficient for stable learning we observe that the Wasserstein, IPM, and MMD losses respectively satisfy (D1), (D2), and (D3) individually, but not all of of them the same time. Using techniques from convex analysis, convert these three GAN losses into three regularizers that, when applied simultaneously. causes the resulting loss satisfy all the three conditions. Here, we only outline the technique; the specifies of each case are deferred to Soc
arbitrary loss function J, thereby stabilizing training. In Section 2
We start with an arbitrary base loss function to be regularized. Next, we take an existing GAN loss that satisfies the desired regularity condition and convert it into a regularizer function R M(X)- - R. Then, we consider + R, which denotes the inf-convolution defined as
(J ) R)( = inf J(E) + R(g - E)
(5)
ÊEM(X)
This new function J ④ R inherits the regularity of R, making it a stable candidate as a GAN loss. Moreover, because the onnvolooottionn a commutative operation, we can sequentially apply multi- ple regularizers R1, Rg, and R3 without destroying the added regularity, In particular, if we carefully choose functions R1. R2, and Rs, then J J + R1 + R2 @ Rs will satisfy (D1), (D2), and (D3) simultaneously. Moreover, under some technical assumptions, this composite function J inherits the original minimizers of J, making it sensible GAN loss:
Proposition 2 (Invariance of minimizers). Let R1 ( == |KE||RR R2(E) == |1. and Rs(E)
E be the three regularizers defined by (8) 112 and (19) respectively. Assume that : M(X) )- R has a unique minimizer at μ4 with (po)
and (() 2 clp Poll for some c > 0. Then the inf-convolution J = + Ri + Rg @ Rs has a unique minimizer at po with ((HO = O.
The duality formulation 4 provides practical method for minimizing this composite function. We leverage the duality relation (J + R @ R2 + R3)* = + R + R2 + R3 and apply 4
/ 1 dy
inf (J 1
Rí + R2
Ra)(2) = inf sup sup 1
J (4p RT(()) Rg((p) Rg(
(6)
inf sup I - 1 Rg(1))
This minimax problem can be seen GAN whose discriminator objective has three added regu- larization terms.
The concrete form of these regularizers summarized in Table recover standard techniques for stabilizing GANs:
Notably, we observe that
(D1) is enforced by Lipschitz constraints (i.e., spectral normalization) on the discrimi- nator.
(D2) is enforced by spectral normalization and a choice of Lipschitz, smooth activation functions for the discriminator.
Table 3: Smoothness-inducing regularizers and their convex conjugates. To enforce regularity condition on a loss function J, we take a source loss that satisfies and view it as a regularizer R. We then consider the inf-convolution J @ R, which corresponds to added regularization term R on the discriminator sp These regularization terms correspond to existing GAN techniques.
Purpose
Source loss
R(E)
Rd (xp)
GAN techniques
(D1)
W1
|
x(1ss11aap 1}
spectral norm
(D2)
IPMs
Ellss
xly E S}
smooth activations, spectral norm gradient penalties
(D3)
MMD
1 |1
5

---

Published as a conference paper at ICLR 2020
(D3) is enforced by gradient penalties on the discriminator.
Our analysis therefore puts these regularization techniques firm theoretical foundation (Propo- sition Tand Theorem D and provides insight into their function.
ENFORCING (DI) WITH LIPSCHITZ CONSTRAINTS
In this section, we show that enforcing (D1) leads to techniques and notions commonly used to sta- bilize GANs, including the Wasserstein distance, Lipschitz constraints and spectral normalization. Recall that (D1) demands that the optimal discriminator 2 is Lipschitz:
(D1) (xx is a-Lipschitz for all μ E P(X), i.e. (x) (w) aa| y||..
If i is differentiable, this is equivalent to that the optimal discriminator has gradient with bounded norm. This is sensible criterion, since discriminator whose gradient norm is too large may push the generator too hard and destabilize its training.
To check (D1), the following proposition shows that suffices to check whether [J(p) J(v) s a (v, v) for all distributions p, v:
Proposition 3. (D1) holds if and only if J is a-Lipschitz w.r. the Wasserstein-I distance.
Arjovsky et al. 2017) show that this property does not hold for common divergences based on Kulbback-Leibler
divergence, while it does hold for the Wasserstein-1 distance. Indeed, is this desirable property that motivates their introduction of the Wasserstein GAN. Framed in our context, their result is summarized follows:
Proposition 4. The minimax and non-saturating GAN losses do not satisfy (DI) for some μoo-
Proposition 5. The Wasserstein GAN loss satisfies (DI) with a for any po-
Our stability analysis therefore deepens the analysis of Arjovsky al. (2017) and provides alter- native reason that the Wasserstein distance is desirable as a metric: it is part of a sufficient condition that ensures stationarity of gradient descent.
4.1 FROM WASSERSTEIN DISTANCE TO LIPSCHITZ CONSTRAINTS
Having identified the Wasserstein GAN loss one that satisfies (D1), next follow the strategy outlined in Section to convert it into a regularizer for an arbitrary loss function. Towards this, we define the regularizer R1 :M(X) - R and compute its convex conjugate Ri C(X) R:
/ f dg,
0
| S a otherwise.
(E = a|K]|kR a sup
RT(())
(8)
fEC(X)
This norm is the Kantoruvich-Rubintee norm (KR norm), which extends the Wasserstein-1 distance to M(X); it holds that || (oju-v/es w|KKR= = Wi v)) for μl, v E P(X). Then, its inf-convolution with arbitrary function inherits the Lipschitz property held by R1:
Proposition (ausch-Hasddorf). Let J M(X) + be a function, and define J == J@R Then a-Lipschitz w.r.. the distance induced by the KR norm, and hence the Wasserstein-1 distance when restricted to P(X).
Due to Proposition 3 we now obtain a transformed loss function J that automatically satisfies (DI). This function is a generalization of the Hausdoff envelope (see Chapter 9 in Rockafeller & Wets 1998)), also known as Lipschitz regularization or the McShane- McShane-Whinee extension (McShane)
1934
Whitney 1934 Kirszbraun
1934 Hiriart- Urrutty 1980).
The convex conjugate computation in 8 shows that J can be minimized in practice by imposing Lipschitz constraints on discriminators. Indeed, by (4).
inf (J @ ail [[kk))))))) = inf sup Eur (x)) J+(() x(1l<lliap S <a)

---

Published as a conference paper at ICLR 2020
inf sup 1 ypr llse pellias
(p.
(10)
Farnia & Tse (2018) consider this loss J in the special of an f-GAN with J(z) (J, they showed that minimizing J corresponds discriminator to be a-Lipschitz. We show that this technique is in fact generic for any J: minimizing the transformed loss can be achieved by training the GAN as normal, but imposing Lipschitz constraint the discriminator.
(()mp)o po);
training a f-GAN normally but constraining the
Our analysis therefore justifies the use Lipschitz constraints, such as spectral normalization (Myy- ato et al., 2018) and weight clipping (Arjovsky & Bottou, 2017), for general GAN losses. However, Theorem I also suggests that applying only Lipschitz constraints may not be enough to stabilize GANs, (D1) alone does not ensure that the GAN objective is smooth.
5 ENFORCING (D2) WITH DISCRIMINATOR S.MOTHNESSS
(D2) demands that the optimal discriminator 4 is smooth:
(D2) + v (x) is $1 -Lpiscchitz for all P(X), i..., [)) - v S 811lz vll2-
Intuitively, this says that for a fixed generator μu, the optimal discriminator 4 should not provide gradients that change too much spatially.
Although the Wasserstein GAN loss (D1), we see that it, along with the minimax GAN and the non-saturating GAN, do not satisfy (D2):
Proposition The Wasserstein, minimax, and satusaatutiing GAN losses do not satisfy (D2) for some po.
We now construct loss that by definition satisfies (D2). Let S be the class of 1-smooth functions, that is, for which [ fz) V (1))ll < || y/12, and consider the integral probability metric
(IPM) (Müller 1997) w.r.t. S, defined by
/ fdu - Idv.
f dv.
IPMs(u,)) = sup
(11)
ses.
The optimal discriminator for the loss IP,s( (o) is the function that maximizes the supremum in the definition. This function by definition belongs to S and therefore 1-smooth. Hence, this IPM loss satisfies (D2) with 31 1 by construction.
5.1 FROM INTEGRAL PROBABILITY METRIC TO SMOOTH DISCRIMINATORS
Having identified the IPM-based loss as one that satisfies (D2), we next follow the strategy outlined in Section to convert it into regularizer for arbitrary loss function. To do so, we define regularizer Rg M(X) > IR and compute its convex conjugate R3
C(X) +
/ /
0
4p E BiS
(E) = B-1kEls- = B1 sup fES
(5( = Do otherwise.
(12)
The norm is the dual norm to S, which extends the IPM to signed measures; it holds that IPMs v) || vils- for μ.v P(X). Similar to the situation the previous section, inf-convolution preserves the smoothness property of Rz:
Proposition 8. Let J M(X) R be convex, proper, lower semicontinuous functiooon and define J J + By Then the optimal discriminator for j is 31-smooth.
Applying 4 and [2), we see that we can minimize this transformed loss function by restricting the family of discriminators only 31 3m-smooth discriminators:
inf (J + B1ll-Ils (H) = inf sup Ez>n(<(<)) - J (4p) - x(y e BiS)
(13)
inf sup J [p, s
(14)
In practice, we can enforce this by applying spectral normalization MMyato et al. (0188) and using a I Lipschitz, smooth activation function such EL.U (Clevert et al. 2016) sigmoid.

---

Published as a conference paper at ICLR 2020
Proposition 9. Let f R - RR be neural network consisting of l layers whose linear transfor- mations have spectral norm and whose activation functions are 1-Lipschitz and 1-smooth. Then f is smoothhh
ENFORCING (D3) WITH GRADIENT PENALTIES
(D3) is the following smoothness condition:
(D3) μ + (x) is Bz-Lipschita, for any x i.e., [ (2 & W,Wi(,
(D3) requires that the gradients of the optimal discriminator do not change too rapidly in response to changes in μ. Indeed, if the discriminator's s gradients are too sensitive to changes in the generator, the generator may not be able accurately follow those gradients it updates itself using finite step size. In diiee--imensional optimization function ff Rd + R, this condition is analogous to f having Lipschitz gradient.
We now present an equivalent characterization of (D3) that is easier to check in practice. We define the Bregman divergence of convex function J (X) + RR by
D)(u, = J()) J(v- - J(m) - (1(x) d()-)) 14)
(15)
where by is the optimal discriminator for J at Then, (D3) is characterized in terms of the Bregman divergence and the KR norm as follows: Proposition 10. Let M(X) T be conver function. Then J satisfies (D3) if and only if Du(2, (4) S || vllknn for all p.v E M(X).
It is straightforward to compute the Bregman divergence corresponding several popular GANs:
2 Dis(- m1) (V, ()) DKL ( + 2 || 1/ (o) + (K
(16)
D ( t ()) (o) 11) = ( + 4 _ }2)), (MMDD (v. (1) 1MMD (v, 14).
(17)
(18)
The first two Bregman divergences are not bounded above by || - v for reasons similar to those discussed in Section 4 and hence: Proposition 11.
The minimax and non-saturating GAN losses do not satisfy (D3) for some Po-
Even so, the Bregman divergence for the non-saturating loss is always less than that of the minimax GAN, suggesting that the non- saturattutin loss should be stable in more situations than the minimax GAN. On the other hand, the MMD- loss (Li et al. 2013) does satisfy (D3) when its kernel is the Gaussian kernel K K(x, y) e =||--
Proposition 12. The MMD loss with Gaussian kernel satisfies (D3) with Br 2T for all po-
6.1 FROM MAXIMUM MEAN DISCREPANCY TO GRADIENT PENALTIES
Having identified the MMD-based loss as one that satisfies (D3), we next follow the strategy outlined in Section 3 convert it into regularizer for arbitrary loss function. To do so. define the regularizer Rg MMX) > IR and compute its convex conjugate R C(X) + R:
B2 4T
Ra(E)
Rg(p))
B2 |1
(19)
The norm the norm of reproducing kernel Hilbert space norm (RKHS) H with Gaussian kernel; this norm extends the MMD to signed measures, it holds that MMD v) |/ Đ
for μ4, 1 E P(X). Here, f f K(x,)) E(dx) E H denotes the mean embedding of a signed measure & & M(X); we also adopt the convention that ||v/|| = oc if &o & H. Similar to the situation in the previous sections, inf-convolution preserves the smoothness property Rs:
Proposition 13
regularization). Suppose J M(X)= + I is convex, and define j := J @ R3. Then J is convex, and D jv, v 1) < vlIR
8

---

Published as a conference paper at ICLR 2020
By Proposition I0, this transformed loss function satisfies (D3), having inherited the regularity prop- erties of the squared MMD. This transformed function is a generalization of Moreau-Yossee larization or the Moreau envelope (see Chapter 1 in Rockafeller & Wets (1998). It is well-known that the case of a function / II - Ik, this regularization results in a function with I Lipschitz gradients, is unsurprising that this property carries over to the infniteeddimnsionall case.
regu-
Applying and 19 we see that the transformed loss function can be minimized as a GAN by implementing RKHS squared norm penalty on the discriminator:
inf (J + All (1) = inf sup Ex~ulo(x) - (1))) - 11
(20)
Computationally, the RKHS norm is difficult to evaluate. We propose taking advantage of the fol- lowing infinite series representation of f in terms of the derivatives of f (Fasshauer & Ye 2011 Novak et al. 2018):
Proposition 14. Let H. be an RKHS with the Gaussian kernel K(x, v) f E H.
011 Then for
11 E (4m)
E tha
|1th
She (((e))
(21)
li=1 kip
= I1 + + [IV
1677 V| fIli2 + other terms.
(22)
In an ideal world, we would use this expression as penalty on the discriminator to enforce (D3). Of course, as an infinite series, this formulation computationally impractical. However, the first two terms are very close to common GAN techniques like gradient penalties (Gulrajani et al. 2017) and penalizing the output of the discriminator (Karras et al. 2018). We therefore interpret these common practices as partially applying the penalty given by the RKHS norm squared, approximately enfore- ing (D3). We view the choice of only using the leading terms as a disadvantageous but practical necessity.
Interestingly, according to our analysis, gradient penalties and spectral normalization are not inter- changeable, even though both techniques were designed to constrain the Lipschitz constant of the discriminator. Instead, our analysis suggests that they serve different purposes: gradient penalties enforce the variational smoothness (D3), while spectral normalization enforces Lipschitz continuity (DI). This demystifies the puzzling observation of Miyato (2018) that GANs using only spectral normalization with WGAN loss do seem to train well; also explains why using both spectral normalization and gradient penalty is a reasonable strategy. It also motivates the use of gradient penalties applied to losses other than the Wasserstein loss (Fedus et 2018).
7 VERIFYING THE THEORETICAL LEARNING RATE
In this section, we empirically test the theoretical learning rate given by Theorem[aad Proposition as well as regularization scheme (7) based on inf-convolutions, We approximately implement
our composite regularization scheme on a trivial base loss of J(z)= x(u = = by alternating stochastic gradient steps
inf sup Ezz)(((() - Ex-pa
π Exzn (xx)) + 4T [VP(()))
(23)
3r
where ğ is random interpolate between samples from j and (Ag. as used in Guirajani et al. 2017 The regularization term is a truncation of the series for the squared RKHS norm (22) and approx- imately enforces (D3). The discriminator is 7-layer convolutional neural network with spectral normalization and ELU activations, an architecture that enforces (D1) and (D2). We include a final
scalar multiplication by a that by Proposition B1 7a. We take two discriminator steps for every generator step, to better approximate our assumption of an optimal discriminator.
Whereas Miyato et al. 2018) divide each layer by the spectral norm of the convolutional kernel, we divide by the spectral norm of the convolutional operator itself, computed using the same power iteration algorithm applied to the operator. This is so that the layers truly 1-Lipschitz, which is critical for our theory.

---

Published as a conference paper at ICLR 2020
500
400
6011
200-
100
10P
11f
10
3/70
Figure 1: FID of simple particle generators with various learning rates. The horizontal axis shows the ratio 7/7o between the actual learning rate y and the theoretical learning rate To suggested by Theorem and Proposition |
The vertical axis shows the FID after 100,000 SGD iterations.
For the generator, we use an extremely simple particle-based generator which satisfies (GI) and (G2), in order minimize the number of confounding factors in our experiment. Let w be the discrete uniform distribution on Z f1....,NY N... For an N x d matrix 0 and E Z, define Sa Rd so that fo(=) the æth row of 0. The particle generator μi = Sorw satisfies (G1) with VN since
[=]l)f((=)= (=) N E10 02112
102-011123
VN 10 0'11r,
(24)
and it satisfies (G2) with 0, since Dofo(=) is constant w.r.t. 0. With this setup, Theorem suggests a theoretical learning rate of
To aB A3 32) 7a + 32
(25)
We randomly generated hyperparameter settings for the Lipschitz constant a, the smoothness con- stant B2, the number of particles N, and the learning rate y. We trained each model for 100,000 steps on CIFAR-10 and evaluate each model using the Fréchet Inception Distance (FID) of Heusel al. 2017). We hypothesize that stability is correlated with image quality; Figure D plots the FII) for each hyperparameter setting in terms of the ratio of the true learning rate and the theoretically motivated learning rate To- We find that the best FID scores are obtained in the region where 7/%0 is between and 1000. For small learning rates 7/10 < 1, we observe that the convergence is slow to make a reasonable progress on the objective, whereas the learning rate gets larger 7/%0 > 1, we observe a steady increase in FID, signalling unstable behavior. It also makes sense that learning rates slightly above the optimal rate produce good results, since our theoretical learning rate is conservative lower bound. Note that our intention is to test our theory, not to generate good images, which is difficult due to our weak choice generator. Overall, this experiment shows that theory and regularization scheme are sensible.
8 FUTURE WORK
Inexact gradient descent In this paper, we employed several assumptions in order to regard the GAN algorithm gradient descent. However, real-world GAN algorithms must be treated as "in- exact" descent algorithms. As such, future work includes: (i) relaxing the optimal discriminator assumption (cf. (Sanjabi et al. (2018)) providing stability result for discrete simultaneous gradi- ent descent (cf. continuous time analysis in Nagarajan & Kolter (207);; Mescheder et al. (2018). (ii) addressing stochastic approximations of gradients (i.e., SGD), and (ili) providing error bounds for the truncated gradient penalty used in 23
Generator architectures Another important direction research to seek more powerful gen- erator architectures that satisfy our smoothness assumptions (G1) and (G2). In practice, generators are often implemented as deep neural networks, and involve some specific architectures such as de- convolution layers (Radford et al. 2015) and residual blocks (e.g., Gulrajani al. (2017); Miyato et al. (2018)). In this paper, we did not provide results on the smoothness of general classes gen- erators, since focus is analyze stability properties influenced by the choice of loss function J (and therefore optimal discriminators). However, our conditions (GI) and (G2) shed light on how to obtain smoothly parameterized neural networks, which is left for future work.
10

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGMENTS
We would like thank Kohei Hayashi, Katsuhiko Ishiguro, Masanori Koyama, Shin-ichi Maeda, Takeru Miyato, Masaki Watanabe, and Shoichiro Yamaguchi for helpful discussions.
REFERENCES
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient Flows in Metric Spaces and in the Space of Probability Measures. Birkhäuser, second edition, 2008.
Michael Arbel, Dougal Sutherland, Mikolaj Binkowski, and Arthur Gretton. On gradient regular- izers for MMD GANs. In Advances in Neural Information Processing Systems, pp. 6700-6710, 2018.
Martin Arjovsky and Leon Bottou. Towards principled methods for training generative adversarial networks. In International Conference Learning Representations, 2017.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, pp. 214-223, 2017.
Heinz H. Bauschke and Patrick L. Combettes. Conver Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2011.
Dimitri P. Bertsekas. Nonlinear Programming. Athena Scientific, 2nd edition, 1999.
Leon Bottou, Martin Arjovsky, David Lopez-Paz. and Maxime Oquab. Geometrical insights for implicit generative modeling. In Braverman Readings in Machine Learning. Key Ideas from Inception to Current State, pp. 229-268. Springer, 2018.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 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.
Sébastien Bubeck, Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-357) 2015.
Casey Chu, Jose Blanchet, and Peter Glynn. Probability functional descent: A unifying perspective on GANs, variational inference, and reinforcement learning. In International Conference on Machine Learning, 2019.
Djork-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (ELUs). 2016.
Farzan Farnia and David Tse. A convex duality framework for GANs. In Advances in Neural Information Processing Systems, pp. 5248-5258, 2018.
Gregory E Fasshauer and Qi Ye. Reproducing kernels of generalized Sobolev spaces via a Green function approach with distributional operators. Numerische Mathematik, 119(3))85--61, 2011.
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 on Learning Representations, 2018.
Ian Goodfellow, Jean Pouget-Abadie, Mchdi 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.
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(1):723-773, 2012.
Paulina Grnarova, Kfir Y Levy, Aurelien Lucchi, Thomas Hofmann, and Andreas Krause. An online learning approach to generative adversarial networks. International Conference on Learning Representations, 2018
11

---

Published as a conference paper at ICLR 2020
Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Im- proved training of Wasserstein GANs. In Advances in Neural Information Processing Systems, pp. 5767-77777, 2017.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by two time-scale update rule converge to a local nash equilibrium. In Advances in Neural Information Processing Systems, 2017.
J-B Hiriart- HiriaattUrruty, Extension of Lipschitz functions. Journal of Mathematical Analysis and Appli- cations, 77(2)539-554, 1980.
Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen. Progressive growing of GANs for im- proved quality, stability, and variation. In International Conference on Learning Representations, 2018.
M Kirszbraun. Über die zusammenziehende und Lipschitzsche Transformationen. Mathematicae, 22(1):77-108, 1934.
Fundamenta
Naveen Kodali, Jacob Abemeety,, James Hays, and Zsolt Kira. On convergence and stability of GANs. arXiv preprint arXiv: arXiv:/705.072155 2017.
Chun-Liang Li, Wei-Cheng Chang, Yu Cheng, Yiming Yang, and Barnabas Poczos. MMD GAN: Towards deeper understanding of moment matching network. In Advances in Neural Information Processing Systems, pp. 2203-2213, 2017a.
Jerry Li, Aleksander Madry, John Peebles, and Ludwig Schmidt. On the limitations of first-order approximation GAN dynamics. In International Conference on Machine Learning, 2017b.
Yujia Li, Kevin Swersky, and Rich Zemel. Generative moment matching networks. In International Conference on Machine Learning, pp. 1718-1727, 2015.
Shuang Liu, Olivier Bousquet, and Kamalika Chaudhuri. Approximation and convergence proper- ties of generative adversarial learning. In Advances in Neural Information Processing Systems, pp. 5545-5555555 2017.
Edward James McShane. Extension of range of functions. Bulletin of the American Mathematical Society, 40( 40(12):837-842 1934.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for GANs do actually converge? In International Conference on Machine Learning, 2018.
Takeru Miyato. How to combine WGAN and spectral norm? reseattreseaach/snngn hrrpggan__poooettoo////ussssse
https://githhnn com/ 2018. Accessed: 2019-09-24.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference Learning Representations, 2018.
Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2):429 443, 1997.
Vaishnavh Nagarajan and Zico Kolter. Gradient descent GAN optimization is locally stable. In Advances in Neural Information Processing Systems, 2017.
Erich Novak, Mario Ulirich, Henryk Wožniakowski, and Shun Zhang. Reproducing kemnlss of Sobolev spaces on nd and applications to embedding constants and tractability. Analysis and Applications, 16(05):693-715, 2018.
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.
Frans Olichock, Rahul Savani, Jose Gallego, Elise van der Pol, and Roderich GroB. Beyond local Nash equilibria for adversarial networks. arXiv preprint arXiv: 1806 007207078 2018.
12

---

Published as a conference paper at ICLR 2020
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv: 1511.0644,, 2015.
R. T. Rockafeller and R. J-B Wets. Variational Analysis, volume 317 of Grundlehren der mathema- tischen Wissenschaften. Springer- Verlag, Berlin, Heidelberg, 1998.
Walter Rudin. The Principles of Mathematical Analysis. McGraw Hill New York, 3rd edition, 1964.
Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn, and Jason D Lee. On the convergence and robust- of training GANs with regularized optimal transport. In Advances in Neural Information Processing Systems, 2018.
Aaron Sidford. MS&E 213 / CS 2690 Chapter 5 smooth convex generalizations, 2017. URL
http: / httt::/wwww.c. rwnsiioooooiioooooo..oooo dford. cwm/ cww/chap http:/haapppep_aae__a__e_a 5___t__ed_________________ee____ v7.
Bharath K Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Gert R Lanckriet, and Bernhard
Schölkopf. Kernel choice and classifiability for rkhs embeddings of probability distributions. In Advances in neural information processing systems, pp. 1750-1758, 2009.
Thomas Strömberg. The operation of infimall convolution. Instytut Matematyczny Polskiej Akademi Nauk, 1996. URL httt::://eudml.oogg//e//////////
Thomas Unterthiner, Bernhard Nessler, Calvin Seward, Günter Klambauer, Martin Heusel, Hubert Ramsauer, and Sepp Hochreiter. Coulomb GANs: Provably optimal Nash equilibria via potential fields. In International Conference on Learning Representations, 2018.
Cédrik Villani. Optimal Transport: Old and New. Springer, 2009.
Hassler Whitney. Analytic extensions of differentiable functions defined in closed sets. Transactions of the American Mathematical Society, 36( (6)1),63- 1934.
Xingyu Zhou, On the Fenchel duality between strong convexity and Lipschitz continuous gradient. arXiv preprint
2018
A INF-CONVOLUTION IN Rd
To gain intuition on the inf-convolution, present finite-dimensional analogue of the techniques in Section 3 For simplicity of presentation, we will omit any regularity conditions (e.g.. lower semicontinuity). We refer readers to Chapter 12 of Bauschke & Combettes (001)) for detailed introduction.
Let and R be convex functions on Rdd. The inf-convolution of J and R is function J R defined as
(J R))x) inf J(=) R(x 2). 2ER4
The inf-convolution is often called the epigraphic sum since the epigraph of J R coincides with the Minkowski sum of epigraphs of and R, as and commutative operation; that is, it is always true that (Jı @ J2) ① J3 = Ji + (Jz ① Jz) J1 + J2 @ J3 and J1 @ J2 = J2 @ J1.
The inf-convolution associative
There are two important special cases of inf-convolutions: The first one is the Paush-Hausdorff envelope Jo. which is the inf-convolution between and ai||-112 (a 0). known that Jn becomes a-Lipschitz. The second important example is the Moreau envelope 8 J @ 23 1.112
ie., the inf-convolttion with the quadratic regularizer 1 11.11. The Moreau envelope J always differentiable, and the gradient of J is 3-Lipschitz (thus J is 3-smooth).
28
is worth noting that the set of minimizers does not change after these two operations. More generally, have the following result:
Proposition 15. Let J, R Rd - & be proper and lower semicontinuous functions with min J > -oo and min R = 0. Suppose R(O) and R(x) 2 (([[=||2) for some increasing function R20 R. Then, min J @ R min and arg min J ( R arg min J.
13

---

Published as a conference paper at ICLR 2020
+
2
1
4
+00
+00
too
+00
Figure 2: Illustration of inf-convolutions and their convex conjugates in R. Top row: Generally, inf-convolutions inherit the regularity of their parent functions. In this example, J1(x) = |x| is 1-Lipschitz but not smooth, while J2(x)) x² /2 is 1-smooth but not Lipschitz. The inf-convolution J1 @ J2 is the well-known Huber function, which is both I-Lipschitz and 1-smooth. Bottom row: Convex conjugates of the functions in the top row. The conjugate of J1 @ J2 is given the sum of conjugates (2) = xfl2| | < 1} and (z) = 2² /2.
To sum up. given a function J. we can always construct regularized alternative Jā that is a- Lipschitz and 3-smooth and has the same minimizers as J.
The next question is how implement the inf-convolution GAN-like optimization problems. For this, it is convenient to consider the convex conjugate. Recall that the Penchel-Moreat theorem says that there
duality between a convex function J and its convex conjugate J as J() (I, =) (=)z) and (z) supzeRd (I. 2) - J(x). The important property is that the convex conjugate of the inf-convolution the sum of convex conjugates, that is, we always have
supseR (x,
(J R)* J (2).
This property can be useful for implementing the regularized objective J follows. First, check that the convex conjugates of the norm and the squared norm are given as (II-112)* = x s 1} and (1 1 11-112- Hence, we have
(x) = J + all-112 + 23 1112 (z)= = sup
-
||
a: ||
which means that minimizing J can be recast in min-max problem with the norm clipping and fzrreuularization the dual variable
B COMMON GAN LOSSES
For completeness and clarity, explicitly write out the expressions for the losses listed in Table 1 For more detailed computations of optimal discriminators, see et al. (2019); for more details on the convex duality interpretation, see Farnia & Tse (008).
Minimax GAN Goodffllow et al. (2014) originally proposed the minimax GAN and showed that corresponding loss function for the minimax GAN the Jensen-Shannon divergence, defined as
1
((z)= == Das(u (o) = 2
DKL(H) [ 3, 4 + 240) + DKL (Ho ll 3 + 210).
14

---

Published as a conference paper at ICLR 2020
where μo E P(X) is a fixed probability measure (usually the empirical measure of the data), and DR || 1)) is the
divergence between j and v. The optimal discriminator in the
sense of Definition Tis given as
dp
@ (x)) = log d(p + no)
(x),
where
is the Radon-Nikodym derivative. If and po have densities jux)) and (o(x), then ]utpo)
de
du
m(xr)
d(u + pa) (z) p(z) + mo(r))
optimal discriminator matches that of Goodfellow al. (2044) up constant factor and logarithm. To recover the minimax formulation, the convex duality (4) yields:
inf DJs no) inf sup Ex>ulp(x) - - E (loge/oooog(( 2 log 2)
(Dis(-noo)"(e))
inf sup E (log(1 D(x))) + En [lo D(x)],
#
using the substitution yp log(1 [1 D) log
Non-saturating GAN Goodfellow et al. (2014) also proposed the heuristic non-saturating GAN.
Theorem 2.5 of Arjovsky & Bottou (017) shows that the loss function minimized is
J(n) = DRL(2 + 10 v0) DKL(U (o) Das po)-
The optimal discriminator is
duo (x).
(x)x) log
d(u + no)
Wasserstein GAN Arjovsky et al. (2117) proposed the Wasserstein GAN, which minimizes the Wasserstein-1 distance between the input y and fixed measure po:
(p) == Wi(,, == inf ((..))~=lll ||| l y/l..
where the infimum is taken over all couplings probability distributions over X X whose marginals are and μi respectively. The optimal discriminator & is called the Kantorovich poten- tial in the optimal transport literature (Villani 2009). The convex duality 4 recover the Wasserstein GAN:
inf Wi (1. inf sup (x-plp(())) (Ernjua [x(=) xillellua S 1))
P
(WW(o.))))
inf sup Ba=a(<(1)) E Bz)an(s(x)),
1 Iell
an expression of Kantorovich-Rubinseri duality. The Lipschitz constraint on the discriminator is typically enforced by spectral normalization (Miyato al. 2018), less frequently by weight clipping (Arjovsky et al. 2017), or heuristically by gradient penaluies (Gulrajani et al., 2017) (although this work shows that gradient penalties may serve different purpose altogether).
Maximum mean discrepancy Given positive definite kernel K X x X E, the maximum mean discrepancy (MMD, Gretton et al. (2012)) between μ and v defined by
1 2
J(n) = MMD v)
K(x, v) - v)(aa) (μr (dy))
where (H. 11-11xx) is the reproducing kernel Hilbert space (RKHS) for K. The generative moment- matching network (GMMN, Li et al. (2015) and the Coulomb GAN (Unterthiner et al. 2018) use the squared MMD as the loss function. The optimal discriminator in this case is
y Eyyaa (K(,, y)]
Ey [K(r, y)],
15

---

Published as a conference paper at ICLR 2020
which in constrast to other GANs, may be approximated by simple Monte Carlo, rather than an auxiliary optimization problem.
Note that MMD-GANs (Li et al., 2017a; Arbel al., 2018) minimize modified version of the MMD, the Optimized MMD (Sriperumbudur et al. 2009, Arbel et al. 2018). These MMD-GANs adversarial in way that does not arise from convex duality, theory currently does not apply to these GANs.
Integral probability metrics An integral probability metric (Müller 1997) is defined by
((n) 1PM, po) == sup 5ef / dp f f dpo.
where F is class of functions. The optimal discriminator is the function that maximizes the supre- mum in the definition. The Wasserstein distance may be thought of as an IPM with containing all 1-Lipschitz functions. The MMD may be thought of as IPM with J all functions with RKHS norm at most 1, but no GANs based on MMD are actually trained this way, as it is difficult to constrain the discriminator to such functions.
C OPTIMAL DISCRIMINATOR, ARE FUNCTIONAL DERIVATIVES
Let J P(X) + R be convex function. Recall the definition of the optimal discriminator (Defini- tion T):
/ pd - J(p).
4 E arg max PEC(X)
This definition be understood as infinite dimensional analogue of subgradients. In fact, in inite-dimensional convex analysis, 2 is a subgradient of f I R if and only it can be written z arg max.. (2', (2)). The calculus of subgradients shares many properties with the standard calculus of derivatives, such as chain rules (Rockafeller & Wets 1998). This motivate us investigate derivative-like features of optimal discriminators.
We introduce the functional derivative, also known as the von Mises influence function:
Definition (Functional derivative). Let J P(X) + R be a function of probability measures. We say that a continuous function 42 X + R is functional derivative of J at μ
[p + a J(r)) + Φ d5 0
holds for any = with v E P(X).
Under this definition, optimal discriminators are actually functional derivatives.
Proposition 16 (huu et al. 2019)) Theorem 2). Let J M(X) + P. be a proper. lower semicon-
tinuous, and convex function. If there exists maximizer 2, + I dp (P)), then o is functional derivative of J at in the sense of Definition 3
The following result relates the derivative of the loss function with the derivative of the optimal discriminator:
Proposition 17 (Chu al. (2019), Theorem 1). Let J P(X) R be continuously differentiable, in the sense that the functional derivative Ty exists and (14, v) + ( is continuous. Let
0 + po be continuous in the sense that [[b]]] (Jo- - pa) converges to a weak limit as |h]] - 0. Then, we have
(pe( VgEn~no [d()),
where + =4 up is treated as a function X + R that is not dependent on 0.
We use this important computational tool in many of our proofs. For the case of the generator model 140 = foww, important consequence of Proposition 17 is that
(po()o) = VoR.~w (aaeenn$((oee (f((z))) Ez-. We this fact in the proof of Theorem 1
fols) fole (Jo(())) Dofoo=))
16

---

a-Lipschitz Published as a conference paper at ICLR 2020
D PROOFS FOR SECTIONS AND 2
The following result is well known in the dynamical systems and the optimization literature. For the sake of completeness, we provide its proof.
Proposition (Bertsekas (1999). Proposition 1.2.3). Suppose f R - R is L-smooth and
bounded below. Let Tk-1 Ik
[z(x)) Then [[V + 0 as k oc.
Proof. It is known that if f L-soohth then
L 2 11 =||²
f(v) f(x) + (VI(x), x) +
holds for any y E Rd (see e.g. Lemma 3.4 in Bubeck (2015)). Then, we have
[(x++1) S [xx) + (V (xx) Jk+1 wx) + _ |1 -x
$ f(rk) [<+
2L IIV [xx((1
1
((x) 2L
[V(xx)]1
Summing this inequality over k, we have
1
[V((z)] - f(zn),
2L
km
from which we conclude that
2T (f inf f(x)).
min oskšn-1
[[
Next, we move on to prove Theorem
I which we restate here for readability.
Theorem (Smoothness decomposition for GANs), Let M(X) + R be a convex function whose optimal discriminators 4 X + R satisfy the following regularity conditions:
(DI) x + (x) is a-Lishchitz
(D2) x + V T (x) is 31 B1-Lipschitz
(D3) μ V is -i-sipchhitz w.r.. the 1- L-Wasserstein distance.
Also, let feaw be a family of generators that satisfies:
(G1) 0 + fo(2) is A-Lipschitz in expectation for z ~ w, Le. (zww(llfo, - Soz (=)(la) s A| 82112. and
(G2) 0 Dofo(2) B-Lipschitz in expectation for z w. i.e. Exrw Do, fe, (z)
Da,fe, (2) - B - 02112-
Then + J(po) is I-smooth, with = aB + A2(31 + 12).
Intuitively, Theorem Maan be understood the chain rule. For simplicity, let us consider the smooth- ness of a composite function D G. where D and G are functions on R. A sufficient condition for DoG be smooth is that its second derivative is bounded. For this, suppose that (i)
and B-smooth and (ii) G is A-Lipschitz and B-smooth. By the chain rule, the second derivative is bounded as (D o G) = (D' o G" (D" ()') < aB + A23, which has the same form as the consequence of Theorem For GANs, need somewhat more involved conditions; We need two types of smoothness (D2) and (D3) for the optimal discriminators. To this end, we utilize the
functional gradient point of view that explained in Appendix C
17

---

Published as a conference paper at ICLR 2020
Proof of Theorem we have
First, using the functional gradient interpretation of the optimal discriminator,
Vo, (10,))
(ooT(Ho)))
V no (z)) So V4 noz (foz(z)) Do2
Proposition
E, Erow
V non (fo, (z)) (Do, D82f0z)
p0 (Jo, (2)) - V4pe, (So, (z))) Do2Jo2
+ (V no, (x)) - vHH, non (z))) DøgJool1
E8 V m6o (fe, (2)) (De, fe, De.fellll
(a)
Egnull
V pml (fo, (2)) V$pb, (fo, (2))) Do,fooll
(b)
+ B2nww
V ( pod (fo, (=)) Nop (foz Dugfealll
(c)
By assumption, there are bounded non-negative numbers a, 81, B2, A, and B such that
(D1')
sup sup | (1)(2))12 HEP(X) zmp
(D2')
sup "EP(X)
|| pp(11) - V p (122)l2 S 311l=1 - x2/12
(D3')
sup zeX
V 2 (I) Vo n2 (2)] S (21,
(G1')
A E Nww sup (o.fo lop: and
(G2') Exow Do, fo (=) Do, Soz (z)llop S BI|0 02ll-
Here, we wrote supzon fx) for the essential supremum of w.r.t. μ.. From (D1') and (G2'), the first term (a) is bounded as
B Vo po, (Jo, (=)) (Do, Do Do.Jo))]] aB 0211-
From (D3'), (G1'), and the Cauchy- Schwarz incquality, the second term (b) is bounded as |Benw[[ (fo, (2)) - V noy (z))) Do.fo
<A32W (H4,,
E.A,gEs~wl1f.. (2)1 - 12 02ll.
where the second inequality holds from the following optimal transport interpretation of Wi:
f fI - y11 s Bewwllfa, (z) - (=)]l.
W1 Wi =
inf (XXXXX coupling (40g and
Lastly, from (D2'). (G1') and the Cauchy-Sehward inequality, the term (c) is bounded
|B (V po (Fo, (z)) - V pag (fo, (z))) Do, fo.ll s A (=) (2)1l - A² 11: -021-
Combining the above upper bounds for (a)-(c), we conclude that
[[o,)((Ho)) VogJ(ue,)) < (aB (aB A3 B2) 0211-
PROOFS FOR SECTION 3
In the fnite-dimenssonal case, Proposition 15 says that taking inf-convolution with a "coercive"
regularizer does not change the set of minimizers of the original objective. A similar invariance holds for GAN objectives, which are defined on infiniteddimensinn space signed measures, for the regularizers R1, R2 and R3 introduced in Sections 4 4
18

---

Published as a conference paper at ICLR 2020
Proposition 2 (Invariance of minimizers). Let RE( == |lEl|RR. R2(E) [IEll and Rs(E)
Ellllli be the three regularizers defined by (8) (12). and (19) respectively. Assume that ((X R has a unique minimizer at μi with (
and J(p) 2 cli Pollu for some c > Then the inf-convolution J ib R1 @ R2 1 Rg has unique minimizer at po with J(po)= 0.
Proof. In the following, we endow M(X) with the Gaussian RKHS norm || and for conve- nience II- will refer this norm not otherwise specified. To show the result, we apply Lemmal three times, first on R3 and R1, and then again on R& R₁ and R2, and then finally on R3 R1 e R2 and J(- + po). The result follows from noting that J(u) = R ① R1 @ R2 @ J[ + po)] No).
In order apply the lemma, suffices show that R3 is uniformly continuous on bounded sets and coercive, and that there exist constants and such that (E) 2 ca cillsl and R2(() 2 c2 12l R3 uniformly continuous on bounded sets: suppose ||E|| < C'and |K'Il C: then RR({) Rs(E')
| 1115'1191 = (5 +-. I -115--51 by the Cauchy- Sehhy-- and triangle inequality. Rg is also coercive, Rg(E) || oo when |IEl|
R1 satisfies R1(E) 2 callell by A
Lemma 7 Ra satisfies (2(E) 2 C2 EEll by Lemma
Recall that function F is said to be coercive if F(E) - do when ||E|| 0C.
Lemma 1. Suppose F =M(X)=
R has unique minimizer at O with F(0) = 0. and is uniformly continuous on bounded sets and coercive. Suppose G MMX) - RR has a unique minimizer at with G(D) = 0, and G(-) 2 cll for some e O. Then the inf-convolution F e G has unique minimizer at with (F + (0) = 0, and is uniformly continuous on bounded sets. coercive, and real-valued.
Proof. From Theorem 2.3 of [Strömberg (996).. inf F @ G = 0, and 0 E arg min F @ G. To show that 0 is the unique minimizer, let & E arg min every n there exists an En E MMX) that satisfies
G. From the definition of inf-convolution, for
lim F(E.) + G(g - (n) (F G)( 0. n-000
Since F and G are non-negative, F(C.)) + 0 and G(g - (.) + 0. By our assumption that G(.) 2 ell |I. the latter limit implies that || - + O, which implies that F(c.) - F({) by continuity of F. Comparing our two expressions for the limit of (g.), we find that F(E) 0, which implies that 5 = 0, since F has a unique minimizer at O. Hence arg min F @ G (0).
From Theorem 2.10 of [Strömberg (199)). F @ G is uniformly continuous on bounded sets and real-valued. To show that F + G is coercive, we show the equivalent condition its sublevel sets are bounded (see Proposition 11.11 of Bauschke & Combettes (201T)). That is, show that for all a > 0, there exists a constant such that if (F + G)()) S a, then ||E|| < b. Let a > O, and let E E (XX be such that (F @ G)) < Let 0; from the definition of inf-convolution, there exists E M(X) such that
F(E) G(E - à) (F G) +eaa+e
Because and G are non-negative, we have that
F()) Sa+e, G(E- a t
Using the fact that F is coercive and hence its sublevel sets are bounded, let be such that F(v) < a + then |||||| < b'. By the triangle inequality and our assumption that G(-) 2 cll [].
|E < + llc डl 0 G(g - 1 a+
c
Because this constant is independent of &, this shows that F @ G is coercive.
19

---

Published as a conference paper at ICLR 2020
F PROOFS FOR SECTION 4
Proposition 3. (D1) holds if and only if J is a-Lipschitz w.t. the Wasserstein-1 distance.
Proof. First, check the forward implication:
(J(μ) J(v)] S aWi(u,,)
sup xm
V (x)2(())22 S aa
From the duality between - and L -nors,, we have
sup [ = D p (M:R))) =IV=9(())l=<<uue)) = (
sup
v v(z) du(x)).
(26)
zmp
Below, will abbreviate I1-Ile Rd)
I1. We utilizee the fact that the optimal discriminator
D is the functional gradient of J in the sense of Definition 3 For any 2 0, let μ4, (id + tu) # be the law of x + tw(x) with x ~ nh. Then, 14 converges weakly to ll = Ho as t - 0 since
Wi (1), s (|) O. Applying Proposition 17 to J and 14, have
_e |( 1==
1 + tu(x)) du(z))
- (x) -0()) t=
= dt
=
In particular, the right-hand side of 26 is bounded from above as
sup
V v(x) du((x)
d
sup
J (pt)
11ll dt
lim [(m] - (HH
sup
[|ll t-10
aWi(pe,P) P))
sup
lim 4-1
|1012
t
sup
lim t-50 t
|
which proves the first half of the statement.
For the converse, we borrow some techniques from the optimal transport theory. Let p > and let
W Wp(n, v) denote the Wasserstein-p distance between and v. Suppose that μ4 [0. 1] P(X) an Pp(XX--abslutelly continuous curve, that is, every μ4 has finite p-moment and there exists
E L ([0, 1)) such that (p Me) S J u(r) dr holds for any 0 < s S t < 1. Then, the limit |p'lw, (t) == lim I (Pe4h H4) exists for almost all t E [0, 1] (see Ambrosio et al. (0008)
Theorem 1.2.). Such [д²|ы;; is called the metric derivative of Pt.
Lemma AAmrosso et al. 2008). Theorem 8.3.1). Let μe : [] P(X) be an continuous curve, and let 11 w, I' ([0, 11) be its metric derivative. Then, there exists vector field u (z, t) + (x))) E Rd such that
Vt E LP(NG X), [[vell S (n'lw,(0)
for almost all E [0, 1), and
[. dt p(x, (dr)ddd -- //') (or(z), t))
holds for any cylindrical function s 1).
20

---

Published as a conference paper at ICLR 2020
Given p 1, let Me be Pp(XX-aaboluttely continuous curve such that μ4 μr and 11 Then
L'" di
d ((m) dt
- L [[eller(H)) | rx(ue) dt (J(z) J(z)]
! / /Or. F..V di
[ dt sup (
- J 1ollw, dt sup \Vlpllz))))
where | is the metric derivative. The existence of D2 and the bound [oxllem(ur) S Inblw, is due Lemma Taking the infimum over all possible such curves, we find that
(J(p) J(v) S W v) sup P
To conclude, we consider the limit p 1. Using the fact that q + (1flle is increasing in g. have
(J(M) - J(M) < Wp(,,D) sup V 1 S aW (W,(H,
Then
- - -(v)] s inf aW (W,(),)) p>l
inf inf || 111--vlen vller(s) nEll(u.)) p>1
inf ||x- vIlz TEMl(W))
= =WWi(p
Proposition 4. The minimax and non-saturating GAN losses do not satisfy (DIffor some pa- Proposition 5. The Wasserstein GAN loss satisfies (DI) with a for any poo
Proof for Proposition 4 and Proposition The counterexample for Proposition fication Example of Arjovsky et al. (2017). Let 8, denote the distribution that outputs x E IR with probability 1. Then, we have
4 is a slight simpli-
log
x ##0 0 0,
foo
x # = 0,
Das (Ōx (0)
and Wi (6,, 5p) = |z]-
00
(0
Therefore, for J(n)= = Das(u || 6n), the inequality [J(5,) - J(oo) < oW Wi(C (5n, 6n) cannot hold for sufficiently small * O, because the left-hand side equals log while the right-hand side equals alz). For J(u) = D + 1 60), the inequality will not hold for any * 0.
Next, verify Proposition 5 For (()) Wi (H,, po), we have (()) - ((v) W Wi(P, no)
Wi(K, nо) < W. (w,,, v) by the triangle inequality (see e.g., Section 6 in Villani (2099)). Reversing the roles of and v, we can conclude that [J(z) J(v) s Wi(p, v). The result follows from Proposition 3
Proposition Hausdorfu,,,,,... Let : :M(X) - be a function, and define J == J@R, Then a-Lipschitz w.r.t. the distance induced by the KR norm, and hence the Wasserstein-1 distance when restricted to P(X).
21

---

Published as a conference paper at ICLR 2020
Proof. Observe that by the triangle inequality,
J(n) - J(v) sup inf aW J(() aWi(u,, D)
S (W)((,
" s (upaWi(Hu))
aW)
Interchanging the roles of μ and completes the proof.
Lemma 3. The convex conjugate of > ail |KR is given as + x(llelltap S aa).
Proof. The convex conjugate is
sup |f f dμ - al|A||KR
sup f f fdu 1---0
= suu
du
P
119llaps
sup
sup l|st| Sa
gdj
1
-sup inf Sialllaa
/ I sdu
9 (ddul)
[ I I - gddu)
inf sup Lip a
inf xff = Hol Sa
x(llflltip S <a),
where Sion's minimax theorem ensures that we can swap the inf and the sup.
G PROOFS FOR SECTION 5
Proposition 7. The Wasserstein, minimax, and non-saturating GAN losses do not satisfy (D2) for
some Po-
Proof. First, prove the statement for the Wasserstein GAN. Consider ((n) W1, (M, dg) evalu- ated at μ p= 5-1 + 51, mixture of spikes at +1. The optimal discriminator of J at this mixture the Kantorovich potential that transfers l dg. which is (,)()) [z]. The gradient of this Kantorovich potential is discontinuous at O, and hence not Lipschitz.
For the minimax GAN H()) (as(u po), let μ and μo be probability distributions I whose densities are p(æ) & exp(-Ixl/2) and po(z) x exp(-Ix(), respectively (i.e., Laplace distributions). Then, the optimal discriminator μ is given
(T(x)) 1 log p(x)+pa(x)
p(z)
- log(1 1 + 2 eexp(-(rl/2)) By elementary calculations, we can see that this function is not differ- entiable x which implies that the minimax GAN does not satisfy (D2). For the non-saturating GAN, we obtain a similar result by swapping the role of and μo-
Proposition 8. Let M(X) R. be convex, proper, lower semicontinuous function, and define j = J @ R2, Then the optimal discriminator for J is B1 smooth.
Proof. J is convex, proper, lower semicontinuous. Hence
J(m) (J All - (()))(x) =sup / pd -
6. Then by the envelope theorem, dy is the ip that maximizes the right-hand side, and hence 1 5J F.
8p
22

---

Published as a conference paper at ICLR 2020
Lemma 4. The convex conjugate of 1 B S is + x E (18).
Proof. The proof of Lemma is nearly identical to the proof of Lemma
Proposition Let f Idd + be neural network consisting of k layers whose linear transfor- mations have spectral norm 1 and whose activation functions are 1-Lipschitz and 1-smooth. Then k-smooth.
Proof. In this section, let {(f) and s(f) denote the Lipschitz constant of f and ff respectively. This inequality holds
s(fog) +
(27)
since
[[d(f (x) a(s ())( [d((o(z)))g((z) dd(oo)))d((())
- -1)0:/000000(0000000000000000000
[ldf(o(x)) (000))1066600)111110000000001111 -g((v)
S +(f]ll((x) - -
S (s(f)e(g)² + ((f)s(g))l==vll) vll
Let be elementwise activation function with E(o) s(o) 1, and let A be linear layer with spectral norm 1. Then ((A) = and s s(A) 0, so
{(a A) - (())
s(o A) S ((o) (())s(A) =1
We note that we can use the same value of s(o) whether we consider or IR + R or elementwise as have
RRd Rd, since for an elementwise
[xd do (y)ll2 diag of (xx diag o' (v) l2
diag(o' (x) d'(v))ll
max jo' o'(x) o' a'(us)
max s(o)) Vil
s(a)]læ vlloo
S <(a)]| yl12-
We apply the inequality 27 smooth.
recursively for all k layers to obtain that the entire network is A-
Lemma 5. Let H. be RKHS with the Gaussian kernel. Then |1 S IHMlS..
Proof. It follows from af(x) Ba;
{f,
(k(w.))
that, for f E H.
0z:
0f(x)
Of(y)
- - Σ
Ox.
Öy:
0K (x.
0K 0K(y,))
<
||
Or
Oy:
1H
O2 2
(2 8)
K2
= l
0x,0ū
dr,0ys
Oy,0i.
< Il (T(x, 2) +((,,)))
where म and ý denote copies of and y, and
(K
( v)
T(x, v) = Σ
On,0ā;
dz,dū;
23

---

Published as a conference paper at ICLR 2020
From 30 we find that for Gaussian kernel.
1 σ3 exp T(x, v)
(xpp-11)) (-11--111 v112)
1/
1120 y/1?
2
and thus,
[VVf(x) - vs(iil = V2
| vl1.
0²
This implies that
/ Idu
sup /
v2 dp
|A
sup JEH.
o² llllls..
s
H PROOFS FOR SECTION
6
Lemma 6. The convex conjugate of i + 2 Aallk f + 2t ll
Proof. This proof is generalized from the dimee-dimensional case We can bound the convex conjugate from above by
(Boyd Vandenberghe 2004
sup If f du
2 2 21111[RR]
S sup
[I Lip ||||K
2
|
IRR
S sup =ER
[1llliip=
2
|lfllL1P
11.f1
|1flltup
A
X2
= 2X I1
If is constant, then may choose μ that
sup f f dp [lulkk
>
2
1
20
2x
and we are done.
Otherwise, for f(x) # f(v). let Mr,y be the signed measure given by
|1 Mx.y X(f(x) - (6. - -8y)
Note that
sup 19l
g gdpzw
I
(g(x) (g(x)-9(v) 9(v))
sup
x(f(x) f())) 11l
11
X(((x) f(u)) d(x,y)
and
J f dp = x(((x) (v)) (f(x) ffw)))()))))))()))) = 111111ppp
24

---

Published as a conference paper at ICLR 2020
Then
sup [/ s dp
21 2 21m11ks [R
[f [dpzy
sup ((x)+(())
2 || KRR
HISEE -2 2
(2 I1SI11np [(x) - s(1) 1
d(r,8)
sup f(x)f(1))
2
II
A Gliriii [|5|lrap 1//l )
2A I1.llipp
Proposition 10. Let J M(X) + R be convex function. Then J satisfies (D3) if and only if
D)(1, l1 for for all p,u MXX).
Proof. Recall the definition of the Bregman divergence:
D)(u, == J(v) J(m) - ff (
u).
Proposition 10 claims that the optimal discriminator 4 is 32-smooth as a function of and only
if
$2 1l 1 llikn
VH, e M(X), J(v) J(4) (a(x)) n)
(28)
This proof is generalized from the finite-dimensional case (hou 2018 Sidford 2017). Suppose that V (z) V ( ll2 S 32llp wllKR holds for all Let be (0
be defined
mixture between 1r = (1 - t)p + tv so that
nO Pb in = and
l|++ - MallKR = 11 8/. || v KR.
Then, we have
p)(m,u) 1.'0 di ((x) dt - (i d()
1//0 / m0mm dlu
d(u--d() -1) -1) o u.)
S/' / [com. - -b,)) d(v - (4) dt
10 *xlliip 111e ullkn dt
B2llu /||KR|la // |R dl
1,3 11 VIlRER di
32 || V
Since the choice of μ and v is arbitrary, we have proved (88 by assuming (D2). Next, we move on to prove the converse. Before proceeding, note that the Bregman divergence Dy(H, n1) is always non-negative. In fact, for any nt M(X), we have
/ Dr d(v 4) { du ('(ww)
1 pp J (1
SJ(v)
=J(1)
25

---

Published as a conference paper at ICLR 2020
I -
which implies 11( 2 O.
Choose E (M(X) arbitrarily. If μ4, the inequality || V v S B2ll μllk is trivial, so we assume { + 1l below. By the non-negativity of the Bregman divergence, we have
0 5 (v)
/ ((60) + / 0 (p)(
[vv)
- ((E) + f @Bellv- (() 22155- 11-5-vlll -vllkR
[Tw) + p d(v f
11)
2
d (
1b) / [i0g Du E) +
B2
82 115 VlliRR
J(E) - J(n) -
(29)
2
Since the above inequality holds for all v E M(X), the last expression is still non-negative if we take the infimum over all v. In particular,
/10 -00-- ppp 110g-0 - -E)+ - |15 - -vliRR
inf rEM(X)
2
// [4/ - - E)
32 |1E - 1
sup vEM(X)
2
/ 100 - Del ds
2/2 ||5| RRR
82
=
sup (EM(()
2
110 & li.pp'
232
using Lemma the last equality. Continuing from we have
0 < ((E) ((n) - f d(g 11)
1
11
&ellEAp
2,32
Swapping the roles of μa and &, we obtain a similar inequality. Adding both sides of thus obtained two inequalities, obtain
/ |0g +, - 11) 32 1
0
$ Lip
Finally, we have
1 1el1 E s 32
/ p d(s - (4) < B2 3/211 10 Dell I1E =|lKRR
and hence we have the desired result:
[1 Dg 11.p S BB2115 - MllKRR
Lemma's 7. Let K(x v) = exp(- 1|=-ع11 =xp(-11t--113 20
Then MMD (H. S 12 -
Proof. First, we note that
/
MMD? (1,
K(2, v) (w v) (μ v)(d))
[(((x,)) - K(x',w) v)) (1r - w)([g)) 1110 - v/lKR
sup aigtar
d(I,x')
K(x v) - K( v/) K(x', ((ao.1) K( K(dd./))))) [01] ||p- 1
sup an uu
d(I, x²) d(y, v.)
26

---

Published as a conference paper at ICLR 2020
Next, we show that
(xx, y) ((,,y') - K ((', + K(',, v8)
1
sup xyaa a'
d(x, duy.yy
x²
Because K is differentiable, it suffices check that the operator norm of Oz On K ( y) is bounded. To see this, note that
Zip(K((; (();,))
== sup
|| - x'1l
x
V K (z, y) VyK k (K',(', (2222)122
sup
| x'll
2
S sup IIV K (1lp
where we obtained by the last equality by applying the vector- mean value theorem (Rudin 1964 to t + v, t)x + tx', y) thereby obtaining
[V, - (x',, v)lle V ||0, V, ((1 - 1)x + Lat,,, ,))ll2
= [1(=' - x) V V. V - t)x + tx', 13)
S 1| - xlael V V [(1 t)xr + tæ yop.
Now
Oz, By, K(x,y) = Oz,00 Bng exp
20 (-202
1
Σ
(o )²
On, exp
(-
1
(Ik- -xs²))
- (xgg -1²)
(30)
20
1
1
exp
(ot 3x)²)
[ (I: 11)( Mi) 2 5i5
20
This is the symmetric matrix
1
||
w/ 2
1
(x- 1 y)² -1]. (2
exp
20²
o2
By inspection, we see that x is an eigenvector with eigenvalue 1 exp( |-
){ oz 10 - 1112-
20
1). and the other eigenvectors are orthogonal to r y with eigenvalues - exp(-
|
20
Setting = ||l- and taking the absolute value of the eigenvalues, we see the maximum operator 20 norm over all v, y is equal to
1 e 2|
1
max
sup #20 の3
1/.
sup #20
0
0²
Therefore
c
It is not strictly necessary for the proof to show equality. However, to show equality, let be a unit vector, and set x' y/ 0, and
y tu. Then
K (tu, tu) K(uu, 0) K(0,tu)) (u) + K(0,0)
2 sup
d(tu, 0) d(tu, 0)
150
2 expp
20
sup
1e0
f2
2 2 exp(
1
lim
2nz
(+0
12
2 exp(
12
lim
2m²
2n2
f0
2f
02
27

---

Published as a conference paper at ICLR 2020
where we used I' I'Hôpital's 's rule to evaluate the limit.
Proposition 11. The minimax and non-saturating GAN losses do not satisfy (D3) for some po-
Proof. For the minimax loss, the Bregman divergence is:
1/
1
log
140
dpo
log
du
2
1
Mu
+
V
2 Hu
+ 1
2
log
P4
dpo
log
P
dpl
2 44
+
24
3PO + zH
log
d(v - 11)
2
140 +
1
Ho +
1
./[ log
1/
log 1
log
duo
+
log
dv
+
2
140 +
2
240 + zu"
1
log
14 + μ
d( Pn + 11 + 2
1
/
log "
du
2
P4 +
/
D + Ho jum + 20) + DKL(U 1)),
2
and for the non-saturating loss, the Bregman divergence is
/ log 1/m + j
D Dru(t &- + tmo l1 ml (v,
d(2 + 20)
/ log
1o + 1/2u
dl d(2 200
4d
+ 2
log
d(v - 14)
Po +
/ log
No +
dpo + 2 log 2/4 + fuv du
1
log
2
no
2
= DKL G + 20 l| 2/2 + H0).
Choosing to be not absolutely continuous w.r.t 1uu + 2o makes the Bregman divergence Do,
which is sufficient to show that the Bregman divergence is not bounded by || 2 Proposition 12. The MMD loss with Gaussian kernel satisfies (D3) with B3 2n for all po-
Proof. We work with the Gaussian kernel K(x, y) = 1lx wl12
and use Proposition 10
1 2
/ K(x,v) (v (o)(dz) (v (u- (d)
(MMDD (u.
2 / K(x,W) (H - (o)(dx) (μ - Ho)
/ (K((z))) u(dg))))(d))) K(x, v) (o (v (d(())
/ K(x,y) (v -m)(d)) (v - m)(dg)
2
MMD2 (M,D?(u,,)
1
||
20
where the last line is from Lemma
7 The result follows with (2m)-1/22
The result actually applies more generally for the MMD loss with a differentiable kernel K that satisfies 32 == supz,y
v)ll < co.
28

---

Published as a conference paper at ICLR 2020
Proposition 13 (Moreau -Moreau-ossida regularization), Suppose J MMX) - I is convex, and define == J @ R3. Then J is convex, and D _V, 14) || VllKR.
Proof. We work on the more general case of K(x y) (2TO²) -0/2 exp(pxppp->/ ||=-v] 20
exp(-Ila_11))
and define
+ eL
J(u) = inf ( MMD (4,
a 2
for c = (2
Let n² be the unique minimizer of the infimum, which exists because the function is a strongly convex. By the envelope theorem, we compute that
cL d J[ + ex0 c=0 de 2
||I + EX - 1111 -x--x=111
de
cL
(llH - 1 101122 + 2E(H - 4", x²n + @1xxl1?))
de 2
cLiu ,",xim
cL / (u - p²)) dx.
so
cl(u -()).
Then
6J
2 D)(1,1) j(v) - J(H) -
d(v - 11)
cl.
[J((] cl. 211 p²) 1/ cLips 1¹,, v 1
inf ((D) ||V
J(10) + eL
1
[J((T)
110 1r 10( cI. p., v 14)
cL
1 11/
cL
(2TO²) -d-1222
02 11
1
L |1|
v| li
2
where we used Lemma for the second-to-last line. The proposition follows for a (2xz)-1/2
Regarding this choice of will turn that in the general case, the dual penalty includes numer- ically unfavorable factor of (2mo²)-d/22 dependent the dimension of the problem. In practical applications, such as image generation, d can be quite large, making the accurate computation of (2ma²) d/2 completely infeasible. For numerical stability, we propose choosing the critical param- 1/2, eter a 11/2 which corresponds to the dimension-fr free kernel K(x, y) = e --
Lemma 8. Let H. be an RKHS with continuous kernel K on a compact domain X. The convex conjugate of μ 11 2 is 11 x(J E H).
29

---

Published as a conference paper at ICLR 2020
Proof. First show upper bound for f E Hi
sup [
pd
X 2
21l11
sup (fi A
E1l1113
[1/1|x|1allle 121 2110117
sup
[|fllx
sup =ER
11fll
X
llfllx
2
X²
1
||
2X
To derive lower bound for general f E C(X), we use the Mercer decomposition of the positive definite kernel K,
K(x, v) Σ (o)(()
where 2 0 are cigenvalues and [e complete orthonormal sequence of (2(XX It is well-known that the corresponding RKHS given by
(g. 0i P((() < <oc
H = E (x dr)
{
ni
and the norm of H by
(g. Φ: )
|19 1l
Let f E C(X) c. L2(X, dx) be an arbitrary function. We replace the supremum of the conjugate function
sup
| du
(31)
by μ M(X) that has square-integrable Radon-Nykoding derivative with respect the Lebesgue measure dr, and then we have a lower bound. We use p(x) for the Radon-Nykodin derivative with slight abuse of notation.
Suppose f(x) = Σ () and jux)) = Ei= (r) are the expansion. Note that, since the
kernel embedding is given by
2
M(x = K(o,)) = Σ
(イ))
1=1
the above maximization is reduced to
sup
2 b3.
This is maximized when by a3/(A77) and the maximum value is
1
(32)
21
75
If H. this value is finite, and the lower bound of the conjugate given by is 3. 1f No which is the same as the upper bound. If f & H. the value 32 is infinite, and the conjugate function takes +00.
30

---

Published as a conference paper at ICLR 2020
Proposition 14. Let H. be an RKHS with the Gaussian kernel ((x, v) e -= Then for
f E H.
1lf (4T)
E
110 ... the fllllli (2(8d)
(21)
-i= hip
k=0
= =11fI[aaRR)
+ 45
16
|| 51 ( + other terms.
(22)
Proof. We consider the more general case of ((x,y) = (2Ta²)-ai 4/2 -1 uulp--ull/00 where we have
Il
Σ (202)
E I1 kj
|10b
2. fl
km
R1 toon Aaam
[|] + o I /VIl + o 2 f1l
+ other terms.
Novak et al. (2018) prove this result for a 1. sketch the proof for the general case here. We use the Fourier transform convention that
f(k) (2x) 4/2 [
e(x) ihz dx, [(x) = (2x) 4/2
((k) dk.
Ru
Consider the inner product
/ @'II f(k) @(k) dk, Rd
(f.))
defined for functions ||ll| co. Expanding the exponential in Taylor series, this inner product gives the equation for the norm in the proposition. By use of the Fourier inversion formula, can be shown that Kz) f(x), where
Kz(y) (2mO²) w113
so this an RKHS with the Gaussian kernel.
31


Reviews:
[{"review_id": "ryeniNsQYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper provides new theoretical view on GAN regularisation. However, it lacks proper empirical evaluation and makes an impression of a work in progress. Furthermore, the conclusions lead mostly to common techniques that have already been studied. \n\nPros:\n- Theorem 1 provides sufficient conditions for convergence of generator gradients to zero (under assumption of optimal discriminators).\n- New view on combining loss functions and regularizers via inf-convolutions.\n- Clarification of a difference between gradient penalties and spectal normalization.\n\nCons:\n- No evaluation with respect to any reasonable GAN setting.\n- Proposed regularization technique combines existing methods and does not actually propose new ones.\n- The main insights of sections 4 and 5 are trivial, like enforcing Lipshitzness of optimal discriminator by optimization of only Lipshitz discriminators.\n- It is unclear wheather proposed solutions are practical, e.g. use of smooth activation functions may be costly and may lead to vanishing gradients. Again, experiments would be desired.\n- Same combination of regularization techniques (gradient penalty, spectral norm and MMD loss) has been studied by [1] in various forms (Gradient-Constrained MMD, Scaled MMD). However, there is no discussion of similarities and differences between these works. \n- Submission's main text is 10 pages long without sufficient reasons for that (figures, tables).\n\nDetailed comments:\n(1) End of Section 4: 'Theorem 1 also suggests that applying only Lipschitz constraints is not enough to stabilize GANs'. Theorem 1 is not 'iff', so Lipshitz constraint *may be* not enough.\n(2) Section 6 concludes that penalization of discriminators RKHS's norm is required. It is unclear, however, why discriminator function would belong to such space.\n(3) In Appendix B authors say, in the context of WGAN, that 'The Lipschitz constraint on the discriminator is typically enforced by spectral normalization (Miyato et al., 2018), (...)'. This setting fails, as stated earlier in the Introduction.\n(4) It seems there is conceptual misundersting of what MMD-GANs are in Appendix B. Authors say 'Despite their names, MMD-GANs (Li et al., 2017a; Arbel et al., 2018) typically do not directly minimize the MMD but instead an adversarial version of the MMD'. GANs by definition are adversarial, while optimization against MMD alone is not. Hence, it is *according to their names*, not 'despite'. \nGenerator losses implied by MMD-GANs under assumption of optimal discriminators, have been termed 'Optimized MMD' [1] and studied earlier in [2].\n(5) Given (4), The Table 2. includes MMD as a GAN loss, although authors probably refer to the properties of non-adversarial Generative Moment Matching Networks [3].\n\n\n[1] Michael Arbel, Dougal Sutherland, Mikołaj Binkowski, and Arthur Gretton. On gradient regularizers for MMD GANs. In Advances in Neural Information Processing Systems, pp. 6700–6710, 2018.\n[2] B. K. Sriperumbudur, K. Fukumizu, A. Gretton, G. R. G. Lanckriet, and B. Schölkopf. “Kernel choice and classifiability for RKHS embeddings of probability distributions.” NIPS. 2009\n[3] Yujia Li, Kevin Swersky, Richard Zemel, \"Generative Moment Matching Networks\", ICML 2015.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "Skl_j_8FKB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The work studies the relationship between the stability and the smoothness of GANs based on the proposition which was proposed by Bertsekas . It explains many nontrivial empirical observations when one is training GANs, including both of the necessities of the spectral normalization and the gradient penalty, in a theoretical perspective. And the work points out that most common GAN losses do not satisfy the all of the smoothness conditions, thereby corroborating their empirical instability. Meanwhile, it develops regularization techniques that enforce the smoothness conditions, which can lead to stability of the GAN.\n\nPros\n1. The paper theoretically gives a reasonable explanation of why applying a gradient penalty together spectral norm seems to improve performance of generator.\n2.  The proofs of the theorems and the propositions in this paper are gorgeous and beautiful.\n\nCons\n1. As the paper concludes, in practice, it is impossible to let the generator be trained after the discriminator attain theoretical optimal. As a paper which topic is about the training process of GAN, it is better to account for real situation.\n\n2. The experiment section is too simple and lacks of persuasiveness. The main theorem only gives the sufficiency of those conditions. I think it’s necessary to give an example which can imply that anyone condition is essential.\n\n3. Proposition 9, Proposition 12 and Equation (7) show the equivalence between the condition (D3) and the existence of the regularization term of the reproducing kernel Hilbert space norm of the discriminator. But after this, the paper uses the first order term of the expansion in Proposition 13 to substitute $\\|\\psi\\|_{H}^2$. The condition (D3) doesn't necessarily still hold if only adding the gradient penalty term to the objective function. Why it can be supposed that the first order term of the expansion plays a leading role in penalizing ? Isn't it unconvincing to explain the necessity of the gradient penalty from the perspective of making the condition (D3) true?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BJeJ4c22tH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides a unified theoretical framework for regularizing GAN losses. It accounts for most regularization technics especially spectral normalization and gradient penalty and explains how those two methods are in fact complementary. So far this was only observed experimentally but without any theoretical insight. The result goes beyond that as the criterion could be applied to general convex cost functional.\nThe main general theorem is Theorem 1 which states 3 conditions on the optimal critic and 2 others on the generator. The paper is mainly concerned by the conditions on the optimal critic and show that the first 2 conditions can be achieved by the Spectral normalization, while the last one can be achieved by some gradient penalty.\nThe paper is clearly written, well structured and pleasant to read.\nI have the following two remarks:\n\t- Proposition 8 provides a way to ensure condition 2 holds (beta-smoothness). It requires spectral normalization and smooth activation functions. In practice, while the spectral normalization is important, the choice of the activation is not in general 1-smooth (Leaky-relu for instance). Does it really matter in practice? \n\tSome illustrative experiments could be beneficial to better understand what's happening.\n\t- Is it that hard to obtain generators that satisfy condition G1 and G2, it seems to be a natural consequence on the regularity of the mapping f? If that is the case, it might be worth better explaining how this is challenging.\n\t\nLimitations: The paper considers only the setting where the optimal critic is reached and therefore it is still unclear if the analysis carries on to the training procedures used in practice (non-optimal critic). The authors recognize this limitation and leave it for future work.\n\nOverall, I feel that the paper provides good insights on what regularization is important for training gans and why. For that reason, I think this paper should be accepted.\n\n\n------------------------------------------------------------------------------------------------------------\nRevision:\n\nI think the paper provides a good theoretical contribution in terms of interpreting many of the tricks used for improving GAN training. In fact the paper also suggests some new regularization methods (prop 13 for conditions D3)  which would constrain the RKHS norm of the critic. The authors show how it is related to gradient penalty, in a particular case, but the result also suggests something more general. For instance [1], consider an abstract RKHS space containing deep networks and provide an upper-bound on the rkhs norm of such networks in terms of the spectral norm of their weights and a lower-bound in terms of its Lipschitz constant. \n\nI do agree with reviewer 1 that a better discussion of the connection to [2] should be included since that paper was interested in  ensuring weak continuity of the loss, which can be thought of as  a first requirement to get more regularity of the cost functional.\n\nI still think the paper is worth being accepted and raised my score to 8 as I think the authors addressed the major concerns that were raised. \n\n[1] A. Bietti, G. Mialon, D. Chen, and J. Mairal. A Kernel Perspective for Regularizing Deep Neural Networks.\n[2] Michael Arbel, Dougal Sutherland, Mikołaj Binkowski, and Arthur Gretton. On gradient regularizers for MMD GANs. In Advances in Neural Information Processing Systems, pp. 6700–6710, 2018.\n\n\n\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a theoretical study of what regularizations should be used in GAN training and why. The main focus is that the conditions on the discriminator that need to be enforced, to get the Lipshitz property of the corresponding function that is optimized for the generator. Quite a few theorems and propositions are provided. As noted by Reviewer3, this adds insight to well-known techniques: the Reviewer1 rightfully notes that this does not lead to any practical conclusion. 
Moreover, then training of GANs never goes to the optimal discriminator, that could be a weak point; rather than it proceeds in the alternating fashion, and then evolution is governed by the spectra of the local Jacobian (which is briefly mentioned). This is mentioned in future work, but it is not clear at all if the results here can be helpful (or can be generalized).
 At some point of the paper it gets to "more theorems mode" which make it not so easy and motivating to read. 
The theoretical results at the quantitative level are very interesting.  I have looked for a long time on Figure 1: does this support the claims? First my impression was it does not (there are better FID scores for larger learning rates). But in the end, I think it supports: the convergence for a smaller that $\gamma_0$ learning rate to the same FID indicated the convergence to the same local minima (probably). This is perfectly fine. Oscillations afterwards move us to a stochastic region, where FID oscillates. So, the theory has at least minor confirmation. 


Decision: Accept (Poster)