Smoothness and Stability in GANs

Introduction: taming instability with smoothness

Generative adversarial networks (Goodfellow et al., 2014), or GANs, are a powerful class of generative models defined through minimax game. GANs and their variants have shown impressive performance in synthesizing various types of datasets, especially natural images. Despite these successes, 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 to stabilize GANs training, including studies of new generator/discriminator architectures, loss functions, and regularization techniques. Notably, Arjovsky 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 gradient penalties (Gulrajani et al., 2017) and spectral normalization (Miyato et al., 2018). Indeed, these stabilization techniques have proven essential to achieving the latest state-of-the-art results (Karras et al., 2018; Brock et al., 2019).

On the other hand, a solid theoretical understanding of training stability has not been established. Several empirical observations point to an incomplete understanding. For example, why does applying a gradient penalty together spectral norm seem to improve performance (Miyato et al., 2018), even though in principle they serve the same purpose? Why does applying only spectral normalization with the Wasserstein loss fail (Miyato, 2018), even though the analysis of Arjovsky et al. (2017) suggests it should be sufficient? Why is applying gradient penalties effective, even outside their original context of the Wasserstein GAN (Fedus et al., 2018)?

In this work, we develop a framework to analyze the stability of GAN training that resolves these apparent contradictions and clarifies the roles of these regularization techniques. Our approach considers the smoothness of the loss function used. In optimization, smoothness is a well-known condition 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:

This proposition says that under a smoothness condition on the function, gradient descent with a constant step size $\frac{1}{L}$ approaches stationarity (i.e., the gradient norm approaches zero). This is a rather weak notion of convergence, as 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 to frequently destabilize and diverge during training. To diagnose this instability, we consider the smoothness of the GAN’s loss function. GANs are typically framed as minimax problems of the form

In the remainder of this paper, we investigate whether the smoothness assumption is satisfied for various GAN losses. Our analysis answers two questions:

Which existing GAN losses, if any, satisfy the smoothness condition in Proposition 1?

Are there choices of loss, regularization, or architecture that enforce smoothness in GANs?

As results of our analysis, our contributions are as follows:

We derive sufficient conditions for the GAN algorithm to be stationary under certain assumptions (Theorem 1). Our conditions relate to the smoothness of GAN loss used as well as the parameterization of the generator.

We show that most common GAN losses do not satisfy the all of the smoothness conditions, thereby corroborating their empirical instability.

We develop regularization techniques that enforce the smoothness conditions. These regularizers recover common GAN stabilization techniques such as gradient penalties and spectral normalization, thereby placing their use on a firmer theoretical foundation.

Our analysis provides several practical insights, suggesting for example the use of smooth activation functions, simultaneous spectral normalization and gradient penalties, and a particular learning rate for the generator.

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 minimizes the Jensen–Shannon divergence. Since then, the community has introduced a large number of GAN or GAN-like variants that learn generative models by implicitly minimizing various divergences, including $f$-divergences (Nowozin et al., 2016), Wasserstein distance (Arjovsky et al., 2017), and maximum-mean discrepancy (Li et al., 2015; Unterthiner et 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 topological, geometric, and convexity properties of divergence minimization (Arjovsky & Bottou, 2017; Liu et 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 discriminators, while our analysis addresses them separately.

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 a differing approach from ours, we only briefly mention some results in this area, which typically rely on game-theoretic notions (Kodali et al., 2017; Grnarova et al., 2018; Oliehoek et al., 2018) or local analysis (Nagarajan & Kolter, 2017; Mescheder et al., 2018). Some of these results rely on continuous dynamics approximations of gradient updates; in contrast, our work focuses on discrete dynamics.

2 Notation

Smoothness of GAN losses

This section presents Theorem 1, which provides concise criteria for the smoothness of GAN losses.

Based on this duality, minimizing $J$ can be framed as the minimax problem

recovering the well-known adversarial formulation of GANs. We now define the notion of an optimal discriminator for an arbitrary loss function $J$, based on this convex duality:

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 1. Our analysis will apply to any algorithm in this family of algorithms. See Appendix B for more details on this perspective.

We also formalize the notion of a family of generators:

Now, in light of Proposition 1, we are interested in the smoothness of the mapping $\theta\mapsto J(\mu_{\theta})$, which would guarantee the stationarity of gradient descent on this objective, which in 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 of $\theta\mapsto J(\mu_{\theta})$ into conditions on optimal discriminators and the family of generators.

$x\mapsto\Phi_{\mu}(x)$ is $\alpha$-Lipschitz,

$x\mapsto\nabla_{x}\Phi_{\mu}(x)$ is $\beta_{1}$-Lipschitz,

$\mu\mapsto\nabla_{x}\Phi_{\mu}(x)$ is $\beta_{2}$-Lipschitz w.r.t. the $1$-Wasserstein distance.

Also, let $\mu_{\theta}=f_{\theta\#}\omega$ be a family of generators that satisfies:

Then $\theta\mapsto J(\mu_{\theta})$ is $L$-smooth, with $L=\alpha B+A^{2}(\beta_{1}+\beta_{2})$.

Theorem 1 connects the smoothness properties of the loss function $J$ with the smoothness properties of the optimal discriminator $\Phi_{\mu}$, and once paired with Proposition 1, it suggests a quantitative value $\frac{1}{L}$ for a stable generator learning rate. In order to obtain claims of stability for practically sized learning rates, it is important to tightly bound the relevant constants.

In Sections 4, 5 and 6, we carefully analyze which GAN losses satisfy (D1), (D2), and (D3), and with what constants. We summarize our results in Table 2: it turns out that none of the listed losses, except for one, satisfy (D1), (D2), and (D3) simultaneously with a finite constant. The MMD-based loss satisfies the three conditions, but its constant for (D1) grows as $\alpha=O(\sqrt{d})$, which is an 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.

Theorem 1 decomposes smoothness into conditions on the generator and conditions on the discriminator, allowing a clean separation of concerns. In this paper, we focus on the discriminator conditions (D1), (D2), and (D3) and only provide an extremely simple example of a generator that satisfies (G1) 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.), we leave a detailed analysis of the generator conditions (G1) and (G2) as a promising avenue for future work. Indeed, such analyses may lead to new generator architectures or generator regularization techniques that stabilize GAN training.

Enforcing smoothness with inf-convolutions

In this section, we present a generic regularization technique that imposes the three conditions sufficient for stable learning on an arbitrary loss function $J$, thereby stabilizing training. In Section 2, we observe that the Wasserstein, IPM, and MMD losses respectively satisfy (D1), (D2), and (D3) individually, but not all of of them at the same time. Using techniques from convex analysis, we convert these three GAN losses into three regularizers that, when applied simultaneously, causes the resulting loss to satisfy all the three conditions. Here, we only outline the technique; the specifics of each case are deferred to Sections 4, 5 and 6.

The duality formulation (4) provides a practical method for minimizing this composite function. We leverage the duality relation $(J\oplus R_{1}\oplus R_{2}\oplus R_{3})^{\star}=J^{\star}+R_{1}^{\star}+R_{2}^{\star}+R_{3}^{\star}$ and apply (4):

This minimax problem can be seen as a GAN whose discriminator objective has three added regularization terms.

The concrete form of these regularizers are summarized in Table 3. Notably, we observe that we recover standard techniques for stabilizing GANs:

(D1) is enforced by Lipschitz constraints (i.e., spectral normalization) on the discriminator.

(D2) is enforced by spectral normalization and a choice of Lipschitz, smooth activation functions for the discriminator.

(D3) is enforced by gradient penalties on the discriminator.

Our analysis therefore puts these regularization techniques on a firm theoretical foundation (Proposition 1 and Theorem 1) and provides insight into their function.

Enforcing (D1) with Lipschitz constraints

In this section, we show that enforcing (D1) leads to techniques and notions commonly used to stabilize GANs, including the Wasserstein distance, Lipschitz constraints and spectral normalization. Recall that (D1) demands that the optimal discriminator $\Phi_{\mu}$ is Lipschitz:

(D1) $x\mapsto\Phi_{\mu}(x)$ is $\alpha$-Lipschitz for all $\mu\in\mathcal{P}(X)$, i.e., $|\Phi_{\mu}(x)-\Phi_{\mu}(y)|\leq\alpha||x-y||_{2}$.

If $\Phi_{\mu}$ is differentiable, this is equivalent to that the optimal discriminator has a gradient with bounded norm. This is a sensible criterion, since a 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 it suffices to check whether $|J(\mu)-J(\nu)|\leq\alpha W_{1}(\mu,\nu)$ for all distributions $\mu,\nu$:

(D1) holds if and only if $J$ is $\alpha$-Lipschitz w.r.t. the Wasserstein-1 distance.

Arjovsky et al. (2017) show that this property does not hold for common divergences based on the Kullback–Leibler or Jensen–Shannon divergence, while it does hold for the Wasserstein-1 distance. Indeed, it is this desirable property that motivates their introduction of the Wasserstein GAN. Framed in our context, their result is summarized as follows:

The minimax and non-saturating GAN losses do not satisfy (D1) for some $\mu_{0}$.

The Wasserstein GAN loss satisfies (D1) with $\alpha=1$ for any $\mu_{0}$.

Our stability analysis therefore deepens the analysis of Arjovsky et al. (2017) and provides an alternative reason that the Wasserstein distance is desirable as a metric: it is part of a sufficient condition that ensures stationarity of gradient descent.

Our analysis therefore justifies the use of Lipschitz constraints, such as spectral normalization (Miyato et al., 2018) and weight clipping (Arjovsky & Bottou, 2017), for general GAN losses. However, Theorem 1 also suggests that applying only Lipschitz constraints may not be enough to stabilize GANs, as (D1) alone does not ensure that the GAN objective is smooth.

Enforcing (D2) with discriminator smoothness

(D2) demands that the optimal discriminator $\Phi_{\mu}$ is smooth:

(D2) $x\mapsto\nabla\Phi_{\mu}(x)$ is $\beta_{1}$-Lipschitz for all $\mu\in\mathcal{P}(X)$, i.e., $\lVert\nabla\Phi_{\mu}(x)-\nabla\Phi_{\mu}(y)\rVert_{2}\leq\beta_{1}\lVert x-y\rVert_{2}$.

Intuitively, this says that for a fixed generator $\mu$, the optimal discriminator $\Phi_{\mu}$ 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):

The Wasserstein, minimax, and non-saturating GAN losses do not satisfy (D2) for some $\mu_{0}$.

We now construct a loss that by definition satisfies (D2). Let $\mathcal{S}$ be the class of $1$-smooth functions, that is, for which $\lVert\nabla f(x)-\nabla f(y)\rVert_{2}\leq\lVert x-y\rVert_{2}$, and consider the integral probability metric (IPM) (Müller, 1997) w.r.t. $\mathcal{S}$, defined by

The norm is the dual norm to $\mathcal{S}$, which extends the IPM to signed measures; it holds that $\operatorname{IPM}_{\mathcal{S}}(\mu,\nu)=\lVert\mu-\nu\rVert_{\mathcal{S}^{*}}$ for $\mu,\nu\in\mathcal{P}(X)$. Similar to the situation in the previous section, inf-convolution preserves the smoothness property of $R_{2}$:

Applying (4) and (12), we see that we can minimize this transformed loss function by restricting the family of discriminators to only $\beta_{1}$-smooth discriminators:

In practice, we can enforce this by applying spectral normalization (Miyato et al., 2018) and using a Lipschitz, smooth activation function such as ELU (Clevert et al., 2016) or sigmoid.

Enforcing (D3) with gradient penalties

(D3) is the following smoothness condition:

(D3) $\mu\mapsto\nabla\Phi_{\mu}(x)$ is $\beta_{2}$-Lipschitz for any $x\in X$, i.e., $\lVert\nabla\Phi_{\mu}(x)-\nabla\Phi_{\nu}(x)\rVert_{2}\leq\beta_{2}W_{1}(\mu,\nu)$.

where $\Phi_{\mu}$ is the optimal discriminator for $J$ at $\mu$. Then, (D3) is characterized in terms of the Bregman divergence and the KR norm as follows:

It is straightforward to compute the Bregman divergence corresponding to several popular GANs:

The minimax and non-saturating GAN losses do not satisfy (D3) for some $\mu_{0}$.

Even so, the Bregman divergence for the non-saturating loss is always less than that of the minimax GAN, suggesting that the non-saturating loss should be stable in more situations than the minimax GAN. On the other hand, the MMD-based loss (Li et al., 2015) does satisfy (D3) when its kernel is the Gaussian kernel $K(x,y)=e^{-\pi||x-y||^{2}}$:

The MMD loss with Gaussian kernel satisfies (D3) with $\beta_{2}=2\pi$ for all $\mu_{0}$.

The norm is the norm of a reproducing kernel Hilbert space norm (RKHS) $\mathcal{H}$ with Gaussian kernel; this norm extends the MMD to signed measures, as it holds that $\operatorname{MMD}(\mu,\nu)=\lVert\hat{\mu}-\hat{\nu}\rVert_{\mathcal{H}}$ for $\mu,\nu\in\mathcal{P}(X)$. Here, $\hat{\xi}=\int K(x,\cdot)\,\xi(dx)\in\mathcal{H}$ denotes the mean embedding of a signed measure $\xi\in\mathcal{M}(X)$; we also adopt the convention that $||\varphi||_{\mathcal{H}}=\infty$ if $\varphi\not\in\mathcal{H}$. Similar to the situation in the previous sections, inf-convolution preserves the smoothness property of $R_{3}$:

Applying (4) and (19), we see that the transformed loss function can be minimized as a GAN by implementing an RKHS squared norm penalty on the discriminator:

Computationally, the RKHS norm is difficult to evaluate. We propose taking advantage of the following infinite series representation of $||f||^{2}_{\mathcal{H}}$ in terms of the derivatives of $f$ (Fasshauer & Ye, 2011; Novak et al., 2018):

Let $\mathcal{H}$ be an RKHS with the Gaussian kernel $K(x,y)=e^{-\pi||x-y||^{2}}$. Then for $f\in\mathcal{H}$,

In an ideal world, we would use this expression as a penalty on the discriminator to enforce (D3). Of course, as an infinite series, this formulation is 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 enforcing (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 interchangeable, 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 (D1). This demystifies the puzzling observation of Miyato (2018) that GANs using only spectral normalization with a WGAN loss do not seem to train well; it also explains why using both spectral normalization and a gradient penalty is a reasonable strategy. It also motivates the use of gradient penalties applied to losses other than the Wasserstein loss (Fedus et al., 2018).

Verifying the theoretical learning rate

In this section, we empirically test the theoretical learning rate given by Theorems 1 and 1 as well as our regularization scheme (7) based on inf-convolutions. We approximately implement our composite regularization scheme (7) on a trivial base loss of $J(\mu)=\chi\{\mu=\mu_{0}\}$ by alternating stochastic gradient steps on

and it satisfies (G2) with $B=0$, since $D_{\theta}f_{\theta}(z)$ is constant w.r.t. $\theta$. With this setup, Theorem 1 suggests a theoretical learning rate of

We randomly generated hyperparameter settings for the Lipschitz constant $\alpha$, the smoothness constant $\beta_{2}$, the number of particles $N$, and the learning rate $\gamma$. We trained each model for 100,000 steps on CIFAR-10 and evaluate each model using the Fréchet Inception Distance (FID) of Heusel et al. (2017). We hypothesize that stability is correlated with image quality; Figure 1 plots the FID for each hyperparameter setting in terms of the ratio of the true learning rate $\gamma$ and the theoretically motivated learning rate $\gamma_{0}$. We find that the best FID scores are obtained in the region where $\gamma/\gamma_{0}$ is between 1 and 1000. For small learning rates $\gamma/\gamma_{0}\ll 1$, we observe that the convergence is too slow to make a reasonable progress on the objective, whereas as the learning rate gets larger $\gamma/\gamma_{0}\gg 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 a 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 of generator. Overall, this experiment shows that our theory and regularization scheme are sensible.

Future work

In this paper, we employed several assumptions in order to regard the GAN algorithm as gradient descent. However, real-world GAN algorithms must be treated as “inexact” descent algorithms. As such, future work includes: (i) relaxing the optimal discriminator assumption (cf. Sanjabi et al. (2018)) or providing a stability result for discrete simultaneous gradient descent (cf. continuous time analysis in Nagarajan & Kolter (2017); Mescheder et al. (2018)), (ii) addressing stochastic approximations of gradients (i.e., SGD), and (iii) providing error bounds for the truncated gradient penalty used in (23).

Another important direction of research is to seek more powerful generator 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 deconvolution layers (Radford et al., 2015) and residual blocks (e.g., Gulrajani et al. (2017); Miyato et al. (2018)). In this paper, we did not provide results on the smoothness of general classes of generators, since our focus is to analyze stability properties influenced by the choice of loss function $J$ (and therefore optimal discriminators). However, our conditions (G1) and (G2) shed light on how to obtain smoothly parameterized neural networks, which is left for future work.

Acknowledgments

We would like to thank Kohei Hayashi, Katsuhiko Ishiguro, Masanori Koyama, Shin-ichi Maeda, Takeru Miyato, Masaki Watanabe, and Shoichiro Yamaguchi for helpful discussions.

References

To gain intuition on the inf-convolution, we present a 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 (2011) for a detailed introduction.

The inf-convolution is often called the epigraphic sum since the epigraph of $J\star R$ coincides with the Minkowski sum of epigraphs of $J$ and $R$, as Figure 2 illustrates. The inf-convolution is associative and commutative operation; that is, it is always true that $(J_{1}\oplus J_{2})\oplus J_{3}=J_{1}\oplus(J_{2}\oplus J_{3})=:J_{1}\oplus J_{2}\oplus J_{3}$ and $J_{1}\oplus J_{2}=J_{2}\oplus J_{1}$.

There are two important special cases of inf-convolutions: The first one is the Pasch–Hausdorff envelope $J_{\alpha}$, which is the inf-convolution between $J$ and $\alpha\lVert\cdot\rVert_{2}$ ($\alpha>0$). It is known that $J_{\alpha}$ becomes $\alpha$-Lipschitz. The second important example is the Moreau envelope $J^{\beta}=J\oplus\frac{1}{2\beta}\lVert\cdot\rVert_{2}^{2}$, i.e., the inf-convolution with the quadratic regularizer $\frac{1}{2\beta}\lVert\cdot\rVert_{2}^{2}$. The Moreau envelope $J^{\beta}$ is always differentiable, and the gradient of $J^{\beta}$ is $\beta$-Lipschitz (thus $J^{\beta}$ is $\beta$-smooth).

It is worth noting that the set of minimizers does not change after these two operations. More generally, we have the following result:

To sum up, given a function $J$, we can always construct a regularized alternative $J_{\alpha}^{\beta}$ that is $\alpha$-Lipschitz and $\beta$-smooth and has the same minimizers as $J$.

This property can be useful for implementing the regularized objective $J_{\alpha}^{\beta}$ as follows. First, we can check that the convex conjugates of the norm and the squared norm are given as $(\lVert\cdot\rVert_{2})^{\star}=\chi\{\lVert\cdot\rVert\leq 1\}$ and $(\frac{1}{2}\lVert\cdot\rVert_{2}^{2})^{\star}=\frac{1}{2}\lVert\cdot\rVert_{2}^{2}$. Hence, we have

Appendix B Common GAN losses

For completeness and clarity, we explicitly write out the expressions for the losses listed in Table 1. For more detailed computations of optimal discriminators, see Chu et al. (2019); for more details on the convex duality interpretation, see Farnia & Tse (2018).

Goodfellow et al. (2014) originally proposed the minimax GAN and showed that the corresponding loss function for the minimax GAN is the Jensen–Shannon divergence, defined as

where $\frac{d\mu}{d(\mu+\mu_{0})}$ is the Radon–Nikodym derivative. If $\mu$ and $\mu_{0}$ have densities $\mu(x)$ and $\mu_{0}(x)$, then

so our optimal discriminator matches that of Goodfellow et al. (2014) up to a constant factor and logarithm. To recover the minimax formulation, the convex duality (4) yields:

using the substitution $\varphi=\frac{1}{2}\log(1-D)-\frac{1}{2}\log 2$.

Goodfellow et al. (2014) also proposed the heuristic non-saturating GAN. Theorem 2.5 of Arjovsky & Bottou (2017) shows that the loss function minimized is

Arjovsky et al. (2017) proposed the Wasserstein GAN, which minimizes the Wasserstein-1 distance between the input $\mu$ and a fixed measure $\mu_{0}$:

where the infimum is taken over all couplings $\pi$, probability distributions over $X\times X$ whose marginals are $\mu$ and $\mu_{0}$ respectively. The optimal discriminator $\Phi_{\mu}$ is called the Kantorovich potential in the optimal transport literature (Villani, 2009). The convex duality $\eqref{eq:generic_gan}$ recover the Wasserstein GAN:

an expression of Kantorovich–Rubinstein duality. The Lipschitz constraint on the discriminator is typically enforced by spectral normalization (Miyato et al., 2018), less frequently by weight clipping (Arjovsky et al., 2017), or heuristically by gradient penalties (Gulrajani et al., 2017) (although this work shows that gradient penalties may serve a different purpose altogether).

where $(\mathcal{H},\lVert\cdot\rVert_{\mathcal{H}})$ 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

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 et al., 2018) minimize a modified version of the MMD, the Optimized MMD (Sriperumbudur et al., 2009; Arbel et al., 2018). These MMD-GANs are adversarial in a way that does not arise from convex duality, so our theory currently does not apply to these GANs.

An integral probability metric (Müller, 1997) is defined by

where $\mathcal{F}$ is a class of functions. The optimal discriminator is the function that maximizes the supremum in the definition. The Wasserstein distance may be thought of as an IPM with $\mathcal{F}$ containing all $1$-Lipschitz functions. The MMD may be thought of as an IPM with $\mathcal{F}$ 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.

Appendix C Optimal discriminators are functional derivatives

We introduce the functional derivative, also known as the von Mises influence function:

holds for any $\xi=\nu-\mu$ with $\nu\in\mathcal{P}(X)$.

Under this definition, optimal discriminators are actually functional derivatives.

The following result relates the derivative of the loss function with the derivative of the optimal discriminator:

We use this important computational tool in many of our proofs. For the case of the generator model $\mu_{\theta}=f_{\theta\#}\omega$, an important consequence of Proposition 17 is that

We use this fact in the proof of Theorem 1.

Appendix D Proofs for Sections 1 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.

It is known that if $f$ is $L$-smooth, then

Summing this inequality over $k$, we have

Next, we move on to prove Theorem 1, which we restate here for readability.

First, using the functional gradient interpretation of the optimal discriminator, we have

By assumption, there are bounded non-negative numbers $\alpha$, $\beta_{1}$, $\beta_{2}$, $A$, and $B$ such that

Here, we wrote $\sup_{x\sim\mu}f(x)$ for the essential supremum of $f$ w.r.t. $\mu$. From (D1′) and (G2′), the first term (a) is bounded as

From (D3′), (G1′), and the Cauchy-Schwarz inequality, the second term (b) is bounded as

where the second inequality holds from the following optimal transport interpretation of $W_{1}$:

Lastly, from (D2′), (G1′) and the Cauchy-Schwarz inequality, the term (c) is bounded as

Combining the above upper bounds for (a)–(c), we conclude that

Appendix E Proofs for Section 3

In the finite-dimensional 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 infinite-dimensional space of signed measures, for the regularizers $R_{1}$, $R_{2}$ and $R_{3}$ introduced in Sections 4, 5 and 6:

In order to apply the lemma, it suffices to show that $R_{3}$ is uniformly continuous on bounded sets and coercive, and that there exist constants $c_{1}$ and $c_{2}$ such that $R_{1}(\xi)\geq c_{1}\lVert\xi\rVert$ and $R_{2}(\xi)\geq c_{2}\lVert\xi\rVert$. $R_{3}$ is uniformly continuous on bounded sets: suppose $\lVert\xi\rVert<C$ and $\lVert\xi^{\prime}\rVert<C$; then $|R_{3}(\xi)-R_{3}(\xi^{\prime})|=|\frac{1}{2}\lVert\xi\rVert^{2}-\frac{1}{2}\lVert\xi^{\prime}\rVert^{2}|=|\frac{1}{2}\langle\xi-\xi^{\prime},\xi+\xi^{\prime}\rangle|\leq C\lVert\xi-\xi^{\prime}\rVert$ by the Cauchy–Schwarz and triangle inequality. $R_{3}$ is also coercive, as $R_{3}(\xi)=\frac{1}{2}\lVert\xi\rVert^{2}\to\infty$ when $\lVert\xi\rVert\to\infty$. $R_{1}$ satisfies $R_{1}(\xi)\geq c_{1}\lVert\xi\rVert$ by Lemma 7. $R_{2}$ satisfies $R_{2}(\xi)\geq c_{2}\lVert\xi\rVert$ by Lemma 5. ∎

Recall that a function $F$ is said to be coercive if $F(\xi)\to\infty$ when $\lVert\xi\rVert\to\infty$.

From Theorem 2.3 of Strömberg (1996), $\inf F\oplus G=0$, and $0\in\operatorname*{arg\,min}F\oplus G$. To show that is the unique minimizer, let $\xi\in\operatorname*{arg\,min}F\oplus G$. From the definition of inf-convolution, for every $n$ there exists an $\xi_{n}\in\mathcal{M}(X)$ that satisfies

Since $F$ and $G$ are non-negative, $F(\xi_{n})\to 0$ and $G(\xi-\xi_{n})\to 0$. By our assumption that $G(\cdot)\geq c\lVert\,\cdot\,\rVert$, the latter limit implies that $\lVert\xi-\xi_{n}\rVert\to 0$, which implies that $F(\xi_{n})\to F(\xi)$ by continuity of $F$. Comparing our two expressions for the limit of $F(\xi_{n})$, we find that $F(\xi)=0$, which implies that $\xi=0$, since $F$ has a unique minimizer at . Hence $\operatorname*{arg\,min}F\oplus G=\{0\}$.

Because $F$ and $G$ are non-negative, we have that

Using the fact that $F$ is coercive and hence its sublevel sets are bounded, let $b^{\prime}$ be such that if $F(\nu)\leq a+\epsilon$, then $\lVert\nu\rVert\leq b^{\prime}$. By the triangle inequality and our assumption that $G(\cdot)\geq c\lVert\,\cdot\,\rVert$,

Because this constant is independent of $\xi$, this shows that $F\oplus G$ is coercive.

Appendix F Proofs for Section 4

From the duality between $L^{\infty}$- and $L^{1}$-norms, we have

In particular, the right-hand side of (26) is bounded from above as

which proves the first half of the statement.

For the converse, we borrow some techniques from the optimal transport theory. Let $p>1$, and let $W_{p}(\mu,\nu)$ denote the Wasserstein-$p$ distance between $\mu$ and $\nu$. Suppose that $\mu_{t}:\to\mathcal{P}(X)$ is an $\mathcal{P}_{p}(X)$-absolutely continuous curve, that is, every $\mu_{t}$ has a finite $p$-moment and there exists $v\in L^{1}()$ such that $W_{p}(\mu_{s},\mu_{t})\leq\int_{s}^{t}v(r)\,dr$ holds for any $0\leq s\leq t\leq 1$. Then, the limit $|\mu^{\prime}|_{W_{p}}(t):=\lim_{h\to 0}|h|^{-1}W_{p}(\mu_{t+h},\mu_{t})$ exists for almost all $t\in$ (see Ambrosio et al. (2008), Theorem 1.1.2). Such $|\mu^{\prime}|_{W_{p}}$ is called the metric derivative of $\mu_{t}$.

holds for any cylindrical function $\varphi(x,t)$.

Given $p>1$, let $\mu_{t}$ be a $\mathcal{P}_{p}(X)$-absolutely continuous curve such that $\mu_{0}=\mu$ and $\mu_{1}=\nu$. Then

where $|\mu_{t}^{\prime}|$ is the metric derivative. The existence of $v_{t}$ and the bound $||v_{t}||_{L^{p}(\mu_{t})}\leq|\mu_{t}^{\prime}|_{W_{p}}$ is due to Lemma 2. Taking the infimum over all possible such curves, we find that

To conclude, we consider the limit $p\to 1$. Using the fact that $q\mapsto||f||_{L^{q}(\mu)}$ is increasing in $q$, we have

Next, we verify Proposition 5. For $J(\mu)=W_{1}(\mu,\mu_{0})$, we have $J(\mu)-J(\nu)=W_{1}(\mu,\mu_{0})-W_{1}(\nu,\mu_{0})\leq W_{1}(\mu,\nu)$ by the triangle inequality (see e.g., Section 6 in Villani (2009)). Reversing the roles of $\mu$ and $\nu$, we can conclude that $|J(\mu)-J(\nu)|\leq W_{1}(\mu,\nu)$. The result follows from Proposition 3. ∎

Interchanging the roles of $\mu$ and $\nu$ completes the proof. ∎

where Sion’s minimax theorem ensures that we can swap the inf and the sup. ∎

Appendix G Proofs for Section 5

First, we prove the statement for the Wasserstein GAN. Consider $J(\mu)=W_{1}(\mu,\delta_{0})$ evaluated at $\mu=\frac{1}{2}\delta_{-1}+\frac{1}{2}\delta_{1}$, a mixture of spikes at $\pm 1$. The optimal discriminator of $J$ at this mixture is the Kantorovich potential that transfers $\mu$ to $\delta_{0}$, which is $\Phi_{\mu}(x)=|x|$. The gradient of this Kantorovich potential is discontinuous at , and hence not Lipschitz.

Then by the envelope theorem, $\frac{\delta J}{\delta\mu}$ is the $\varphi$ that maximizes the right-hand side, and hence $\frac{1}{\lambda}\frac{\delta J}{\delta\mu}\in\mathcal{F}$. ∎

The convex conjugate of $\mu\mapsto\beta_{1}\lVert\mu\rVert_{\mathcal{S}^{*}}$ is $\varphi\mapsto\chi\{\varphi\in\beta_{1}\mathcal{S}\}$.

The proof of Lemma 4 is nearly identical to the proof of Lemma 3. ∎

We apply the inequality (27) recursively for all $k$ layers to obtain that the entire network is $k$-smooth. ∎

Let $\mathcal{H}$ be an RKHS with the Gaussian kernel. Then $||\hat{\mu}||_{\mathcal{H}}\leq\frac{\sqrt{2}}{\sigma^{2}}||\mu||_{\mathcal{S}^{*}}$.

It follows from $\frac{\partial f(x)}{\partial x_{i}}=\langle f,\frac{\partial K(x,\cdot)}{\partial x_{i}}\rangle$ that, for $f\in\mathcal{H}$,

From (30), we find that for a Gaussian kernel,

Appendix H Proofs for Section 6

This proof is generalized from the finite-dimensional case (Boyd & Vandenberghe, 2004). We can bound the convex conjugate from above by

If $f$ is constant, then we may choose $\mu=0$ to see that

Otherwise, for $f(x)\neq f(y)$, let $\mu_{x,y}$ be the signed measure given by

Recall the definition of the Bregman divergence:

Proposition 10 claims that the optimal discriminator $\Phi_{\mu}$ is $\beta_{2}$-smooth as a function of $\mu$ if and only if

Since the choice of $\mu$ and $\nu$ is arbitrary, we have proved (28) by assuming (D2).

Next, we move on to prove the converse. Before proceeding, note that the Bregman divergence $\mathfrak{D}_{J}(\nu,\mu)$ is always non-negative. In fact, for any $\mu,\nu\in\mathcal{M}(X)$, we have

which implies $\mathfrak{D}_{J}(\nu,\mu)\geq 0$.

Since the above inequality holds for all $\nu\in\mathcal{M}(X)$, the last expression is still non-negative if we take the infimum over all $\nu$. In particular,

Swapping the roles of $\mu$ and $\xi$, we obtain a similar inequality. Adding both sides of thus obtained two inequalities, we obtain

Because $K$ is differentiable, it suffices to check that the operator norm of $\partial_{x_{i}}\partial_{y_{j}}K(x,y)$ is bounded. To see this, note that

where we obtained by the last equality by applying the vector-valued mean value theorem (Rudin, 1964) to $t\mapsto\nabla_{y}K((1-t)x+tx^{\prime},y)$, thereby obtaining

By inspection, we see that $x-y$ is an eigenvector with eigenvalue $\frac{1}{\sigma^{2}}\exp({-\frac{||x-y||^{2}}{2\sigma^{2}}})(\frac{1}{\sigma^{2}}||x-y||^{2}-1)$, and the other eigenvectors are orthogonal to $x-y$ with eigenvalues $-\frac{1}{\sigma^{2}}\exp({-\frac{||x-y||^{2}}{2\sigma^{2}}})$.

Setting $z=\frac{||x-y||^{2}}{2\sigma^{2}}$ and taking the absolute value of the eigenvalues, we see the maximum operator norm over all $x,y$ is equal to

It is not strictly necessary for the proof to show equality. However, to show equality, let $u$ be a unit vector, and set $x^{\prime}=y^{\prime}=0$, and $x=y=tu$. Then

where we used l’Hôpital’s rule to evaluate the limit. ∎

For the minimax loss, the Bregman divergence is:

and for the non-saturating loss, the Bregman divergence is

We work with the Gaussian kernel $K(x,y)=e^{-\frac{||x-y||^{2}}{2\sigma^{2}}}$ and use Proposition 10:

where the last line is from Lemma 7. The result follows with $\sigma=(2\pi)^{-1/2}$.

The result actually applies more generally for the MMD loss with a differentiable kernel $K$ that satisfies $\beta_{2}:=\sup_{x,y}\|\nabla_{x}\nabla_{y}K(x,y)\|_{2}<\infty$. ∎

We work on the more general case of $K(x,y)=(2\pi\sigma^{2})^{-d/2}\exp(-\frac{\lVert x-y\rVert^{2}}{2\sigma^{2}})$, and define

for $c=\sigma^{2}(2\pi\sigma^{2})^{d/2}$.

Let $\mu^{*}$ be the unique minimizer of the infimum, which exists because the function is a strongly convex. By the envelope theorem, we compute that

where we used Lemma 7 for the second-to-last line. The proposition follows for $\sigma=(2\pi)^{-1/2}$.

Regarding this choice of $\sigma$, it will turn out that in the general case, the dual penalty includes a numerically unfavorable factor of $(2\pi\sigma^{2})^{-d/2}$, dependent on the dimension of the problem. In practical applications, such as image generation, $d$ can be quite large, making the accurate computation of $(2\pi\sigma^{2})^{-d/2}$ completely infeasible. For numerical stability, we propose choosing the critical parameter $\sigma=(2\pi)^{-1/2}$, which corresponds to the dimension-free kernel $K(x,y)=e^{-\pi||x-y||^{2}}$. ∎

Let $\mathcal{H}$ be an RKHS with a continuous kernel $K$ on a compact domain $X$. The convex conjugate of $\mu\mapsto\frac{\lambda}{2}||\mu||^{2}_{\mathcal{H}}$ is $f\mapsto\frac{1}{2\lambda}||f||^{2}_{\mathcal{H}}+\chi\{f\in\mathcal{H}\}$.

First we show an upper bound for $f\in\mathcal{H}$:

To derive a lower bound for general $f\in\mathcal{C}(X)$, we use the Mercer decomposition of the positive definite kernel $K$,

where $\gamma_{i}\geq 0$ are eigenvalues and $\{\phi_{i}\}_{i=1}^{\infty}$ is a complete orthonormal sequence of $L^{2}(X;dx)$. It is well-known that the corresponding RKHS is given by

Let $f\in\mathcal{C}(X)\subset L^{2}(X,dx)$ be an arbitrary function. We replace the supremum of the conjugate function

by $\mu\in\mathcal{M}(X)$ that has a square-integrable Radon–Nykodim derivative with respect to the Lebesgue measure $dx$, and then we have a lower bound. We use $\mu(x)$ for the Radon–Nykodim derivative with slight abuse of notation.

Suppose $f(x)=\sum_{j=1}^{\infty}a_{j}\phi_{j}(x)$ and $\mu(x)=\sum_{j=1}^{\infty}b_{j}\phi_{j}(x)$ are the expansion. Note that, since the kernel embedding is given by

This is maximized when $b_{j}=a_{j}/(\lambda\gamma_{j})$, and the maximum value is

If $f\in\mathcal{H}$, this value is finite, and the lower bound of the conjugate given by is $\frac{1}{2\lambda}\|f\|_{\mathcal{H}}^{2}$, which is the same as the upper bound. If $f\notin\mathcal{H}$, the value (32) is infinite, and the conjugate function takes $+\infty$. ∎

We consider the more general case of $K(x,y)=(2\pi\sigma^{2})^{-d/2}e^{-||x-y||^{2}/2\sigma^{2}}$, where we have

Novak et al. (2018) prove this result for $\sigma=1$. We sketch the proof for the general case here. We use the Fourier transform convention that

defined for functions $||f||<\infty$. 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, it can be shown that $\langle f,K_{x}\rangle=f(x)$, where

so this is an RKHS with the Gaussian kernel. ∎