Approximation and Convergence Properties of Generative Adversarial Learning

Introduction

Generative adversarial networks (GANs) have attracted an enormous amount of recent attention in machine learning. In a generative adversarial network, the goal is to produce an approximation to a target data distribution $\mu$ from which only samples are available. This is done iteratively via two components – a generator and a discriminator, which are usually implemented by neural networks. The generator takes in random (usually Gaussian or uniform) noise as input and attempts to transform it to match the target distribution $\mu$; the discriminator aims to accurately discriminate between samples from the target distribution and those produced by the generator. Estimation proceeds by iteratively refining the generator and the discriminator to optimize an objective function until the target distribution is indistinguishable from the distribution induced by the generator. The practical success of GANs has led to a large volume of recent literature on variants which have many desirable properties; examples are the f-GAN , the MMD-GAN , the Wasserstein-GAN , among many others.

In spite of their enormous practical success, unlike more traditional methods such as maximum likelihood inference, GANs are theoretically rather poorly-understood. In particular, two very basic questions on how well they can approximate the target distribution $\mu$, even in the presence of a very large number of samples and perfect optimization, remain largely unanswered. The first relates to the role of the discriminator in the quality of the approximation. In practice, the discriminator is usually restricted to belong to some family, and it is not understood in what sense this restriction affects the distribution output by the generator. The second question relates to convergence; different variants of GANs have been proposed that involve different objective functions (to be optimized by the generator and the discriminator). However, it is not understood under what conditions minimizing the objective function leads to a good approximation of the target distribution. More precisely, does a sequence of distributions output by the generator that converges to the global minimum under the objective function always converge to the target distribution $\mu$ under some standard notion of distributional convergence?

In this work, we consider these two questions in a broad setting. We first characterize a very general class of objective functions that we call adversarial divergences, and we show that they capture the objective functions used by a variety of existing procedures that include the original GAN , f-GAN , MMD-GAN , WGAN , improved WGAN , as well as a class of entropic regularized optimal transport problems . We then define the class of strict adversarial divergences – a subclass of adversarial divergences where the minimizer of the objective function is uniquely the target distribution. This characterization allows us to address the two questions above in a unified setting, and translate the results to an entire class of GANs with little effort.

We next address convergence in Section 5. We show that convergence in an adversarial divergence implies some standard notion of topological convergence. Particularly, we show that provided an objective function is a strict adversarial divergence, convergence to $\mu$ in the objective function implies weak convergence of the output distribution to $\mu$. While convergence properties of some isolated objective functions were known before , this result extends them to a broad class of GANs. An additional consequence of this result is the observation that as the Wasserstein distance metrizes weak convergence of probability distributions (see e.g. ), Wasserstein-GANs have the weakestWeakness is actually a desirable property since it prevents the divergence from being too discriminative (saturate), thus providing more information about how to modify the model to approximate the true distribution. objective functions in the class of strict adversarial divergences.

Notations

For a topological space $\Omega$, we denote by $C(\Omega)$ the set of continuous functions on $\Omega$, $C_{b}(\Omega)$ the set of bounded continuous functions on $\Omega$, $rca(\Omega)$ the set of finite signed regular Borel measures on $\Omega$, and $\mathcal{P}(\Omega)$ the set of probability measures on $\Omega$.

Given a non-empty subspace $Y$ of a topological space $X$, denote by $X/Y$ the quotient space equipped with the quotient topology $\sim_{Y}$, where for any $a,b\in X$, $a\sim_{Y}b$ if and only if $a=b$ or $a,b$ both belong to $Y$. The equivalence class of each element $a\in X$ is denoted as $[a]=\{b:a\sim_{Y}b\}$.

General Framework

Let $\mu$ be the target data distribution from which we can draw samples. Our goal is to find a generative model $\nu$ to approximate $\mu$. Informally, most GAN-style algorithms model this approximation as solving the following problem

where $\mathcal{F}$ is a class of functions. The process is usually considered adversarial in the sense that it can be thought of as a two-player minimax game, where a generator $\nu$ is trying to mimick the true distribution $\mu$, and a adversary $f$ is trying to distinguish between the true and generated distributions. However, another way to look at it is as the minimization of the following objective function

This objective function measures how far the target distribution $\mu$ is from the current estimate $\nu$. Hence, minimizing this function can lead to a good approximation of the target distribution $\mu$.

This leads us to the concept of adversarial divergence.

Let $X$ be a topological space, $\mathcal{F}\subseteq C_{b}(X^{2})$, $\mathcal{F}\neq\emptyset$. An adversarial divergence $\tau$ over $X$ is a function

Observe that in Definition 1 if we have a fixed target distribution $\mu$, then (2) is reduced to the objective function (1). Also, notice that because $\tau$ is the supremum of a family of linear functions (in each of the variables $\mu$ and $\nu$ separately), it is convex in each of its variables.

Definition 1 captures the objective functions used by a variety of existing GAN-style procedures. In practice, although the function class $\mathcal{F}$ can be complicated, it is usually a transformation of a simple function class $\mathcal{V}$, which is the set of discriminators or critics, as they have been called in the GAN literature. We give some examples by specifying $\mathcal{F}$ and $\mathcal{V}$ for each objective function.

Wasserstein-GAN (WGAN) . Assume $X$ is a metric space.

where $K$ is a positive constant, $\left\lVert\cdot\right\rVert_{\textnormal{Lip}}$ denotes the Lipschitz constant.

WGAN-GP (Improved WGAN) . Assume $X$ is a convex subset of a Euclidean space.

where $U$ is the uniform distribution on $$,$\eta$is a positive constant,$p\in(1,\infty)$.

In order to study an adversarial divergence $\tau$, it is critical to first understand at which points the divergence is minimized. More precisely, let $\tau$ be an adversarial divergence and $\mu^{*}$ be the target probability measure. We are interested in the set of probability measures that minimize the divergence $\tau$ when the first argument of $\tau$ is set to $\mu^{*}$, i.e., the set $\operatorname*{arg\,min}\tau(\mu^{*}||\cdot)=\left\{\mu:\tau(\mu^{*}||\mu)=\inf_{\nu}\tau(\mu^{*}||\nu)\right\}$. Formally, we define the set $\textsc{opt}_{\tau,\mu^{*}}$ as follows.

Let $\tau$ be an adversarial divergence over a topological space $X$, $\mu^{*}\in\mathcal{P}(X)$. Define $\textsc{opt}_{\tau,\mu^{*}}$ to be the set of probability measures that minimize the function $\tau(\mu^{*}||\cdot)$. That is,

Ideally, the target probability measure $\mu^{*}$ should be one and the only one that minimizes the objective function. The notion of strict adversarial divergence captures this property.

Let $\tau$ be an adversarial divergence over a topological space $X$, $\tau$ is called a strict adversarial divergence if for any $\mu^{*}\in\mathcal{P}(X)$, $\textsc{opt}_{\tau,\mu^{*}}=\{\mu^{*}\}$.

For example, if the underlying space $X$ is a compact metric space, then examples (c) and (d) induce metrics on $\mathcal{P}(X)$ (see, e.g., ), therefore are strict adversarial divergences.

In the next two sections, we will answer two questions regarding the set $\textsc{opt}_{\tau,\mu^{*}}$: how well do the elements in $\textsc{opt}_{\tau,\mu^{*}}$ approximate the target distribution $\mu^{*}$ when restricting the class of discriminators? (Section 4); and does a sequence of distributions that converges in an adversarial divergence also converges to $\textsc{opt}_{\tau,\mu^{*}}$ under some standard notion of distributional convergence? (Section 5)

Generalized Moment Matching

To motivate the discussion in this section, recall example (b) in Section 3). It can be shown that under some mild conditions, $\tau$, the objective function of $f$-GAN, is actually the $f$-divergence, and the minimizer of $\tau(\mu^{*}||\cdot)$ is only $\mu^{*}$ . However, in practice, the discriminator class $\mathcal{V}$ is usually implemented by a feedforward neural network, and it is known that a fixed neural network has limited capacity (e.g., it cannot implement the set of all the bounded continuous function). Therefore, one could ask what will happen if we restrict $\mathcal{V}$ to a sub-class $\mathcal{V}^{\prime}$? Obviously one would expect $\mu^{*}$ not be the unique minimizer of $\tau(\mu^{*}||\cdot)$ anymore, that is, $\textsc{opt}_{\tau,\mu^{*}}$ contains elements other than $\mu^{*}$. What can we say about the elements in $\textsc{opt}_{\tau,\mu^{*}}$ now? Are all of them close to $\mu^{*}$ in a certain sense? In this section we will answer these questions.

We will now relate the matching condition to the optimality of the divergence. In particular, define

We will give sufficients conditions for members of $\mathcal{M}_{\mu^{*}}$ to be in $\textsc{opt}_{\tau,\mu^{*}}$.

We now review the examples (a)-(e) in Section 3, show how to write each $f\in\mathcal{F}$ into $m_{\theta}-r_{\theta}$, and specify $\theta^{\mu}_{\nu}$ in each case such that the conditions of Theorem 4 can be satisfied.

GAN. Note that for any $x\in(0,1)$, $\log\left(1/({x(1-x)})\right)\geq\log(4)$. Let $u_{\theta^{\mu}_{\nu}}=\mathbf{\frac{1}{2}}$,

MMD-GAN or Wasserstein-GAN. Let $v_{\theta^{\mu}_{\nu}}=\mathbf{0}$,

We now refine the previous result and show that under some additional conditions on $m_{\theta}$ and $r_{\theta}$, the optimal elements of $\tau$ are fully characterized by the matching condition, i.e. $\textsc{opt}_{\tau,\mu^{*}}=\mathcal{M}_{\mu^{*}}$.

We remark that Theorem 4 is relatively intuitive, while Theorem 5 requires extra conditions, and is quite counter-intuitive especially for algorithms like $f$-GANs.

2 Example: Neural Network f𝑓f-GAN

Now observe that when all the weights before the last layer are fixed, the last layer acts as a discriminator in a linear $f$-GAN. More precisely, let $\Theta_{pre}$ be the index set for the weights before the last layer. Then each $\theta_{\text{pre}}\in\Theta_{\text{pre}}$ corresponds to a feature map $\psi^{\theta_{\text{pre}}}$. Let the linear $f$-GAN that corresponds to $\psi^{\theta_{\text{pre}}}$ be $\tau_{\theta_{\text{pre}}}$, the adversarial divergence induced by the Neural Network $f$-GAN is

Clearly $\textsc{opt}_{\tau,\mu^{*}}\supseteq\bigcap_{\theta_{\text{pre}}\in\Theta_{\text{pre}}}\textsc{opt}_{\tau_{\theta_{\text{pre}}},\mu^{*}}$. For the other direction, note that by Corollary 6, for any $\theta_{\text{pre}}\in\Theta_{\text{pre}}$, $\tau_{\theta_{\text{pre}}}(\mu^{*}||\mu)\geq 0$ and $\tau_{\theta_{\text{pre}}}(\mu^{*}||\mu^{*})=0$. Therefore $\tau(\mu^{*}||\mu)\geq 0$ and $\tau(\mu^{*}||\mu^{*})=0$. If $\mu\in\textsc{opt}_{\tau,\mu^{*}}$, then $\tau(\mu^{*}||\mu)=0$. As a consequence, $\tau_{\theta_{\text{pre}}}(\mu^{*}||\mu)=0$ for any $\theta_{\text{pre}}\in\Theta_{\text{pre}}$. Therefore $\textsc{opt}_{\tau,\mu^{*}}\subseteq\bigcap_{\theta_{\text{pre}}\in\Theta_{\text{pre}}}\textsc{opt}_{\tau_{\theta_{\text{pre}}},\mu^{*}}$. Therefore, by Corollary 6,

That is, the minimizer of the Neural Network $f$-GAN are exactly those distributions that are indistinguishable under the expectation of any discriminator network $v_{\theta}$.

Convergence

Now returning to our adversarial divergence framework. Given an adversarial divergence $\tau$, is it possible that $\tau(\delta_{1}||\delta_{1/n})$ convreges to the global minimum of $\tau(\delta_{1}||\cdot)$? How to we define convergence to a set of points instead of only one point, in order to explain the convergence behaviour of any adversarial divergence? In this section we will answer these questions.

We start from two standard notions from functional analysis.

The definition of weak-* topology and weak convergence respect the topological structure of the sample space. For example, it is easy to check that the sequence of delta distributions $\delta_{1/n}$ weakly converges to $\delta_{0}$, but not to $\delta_{1}$.

Now note that Definition 8 only defines weak convergence of a sequence of probability measures to a single target measure. Here we generalize the definition for the single target measure to a set of target measures through quotient topology as follows.

Let $X$ be a compact metric space, equip $\mathcal{P}(X)$ with the weak-* topology and let $A$ be a non-empty subspace of $\mathcal{P}(X)$. A sequence of probability measures $(\mu_{n})$ in $\mathcal{P}(X)$ is said to weakly converge to the set $A$ if $([\mu_{n}])$ converges to $A$ in the quotient space $\mathcal{P}(X)/A$.

With everything properly defined, we are now ready to state our convergence result. Note that an adversarial divergence is not necessarily a metric, and therefore does not necessarily induce a topology. However, convergence in an adversarial divergence can still imply some type of topological convergence. More precisely, we show a convergence result that holds for any adversarial divergence $\tau$ as long as the sample space is a compact metric space. Informally, we show that for any target probability measure, if $\tau(\mu^{*}||\mu_{n})$ converges to the global minimum of $\tau(\mu^{*}||\cdot)$, then $\mu_{n}$ weakly converges to the set of measures that achieve the global minimum. Formally,

Let $X$ be a compact metric space, $\tau$ be an adversarial divergence over $X$, $\mu^{*}\in\mathcal{P}(X)$, then $\textsc{opt}_{\tau,\mu^{*}}\neq\emptyset$. Let $(\mu_{n})$ be a sequence of probability measures in $\mathcal{P}(X)$. If $\tau(\mu^{*}||\mu_{n})\to\inf_{\mu^{\prime}}\tau(\mu^{*}||\mu^{\prime})$, then $(\mu_{n})$ weakly converges to the set $\textsc{opt}_{\tau,\mu^{*}}$.

As a special case of Theorem 10, if $\tau$ is a strict adversarial divergence, i.e., $\textsc{opt}_{\tau,\mu^{*}}=\{\mu^{*}\}$, then converging to the minimizer of the objective function implies the usual weak convergence to the target probability measure. For example, it can be checked that the objective function of $f$-GAN is a strict adversarial divergence, therefore converging in the objective function of an $f$-GAN implies the usual weak convergence to the target probability measure.

To compare this result with our intuition, we return to the example of a sequence of delta distributions and show that as long as $\tau$ is a strict adversarial divergence, $\tau(\delta_{1}||\delta_{1/n})$ does not converge to the global minimum of $\tau(\delta_{1}||\cdot)$. Observe that if $\tau(\delta_{1}||\delta_{1/n})$ converges to the global minimum of $\tau(\delta_{1}||\cdot)$, then according to Theorem 10, $\delta_{1/n}$ will weakly converge to $\delta_{1}$, which leads to a contradiction.

However Theorem 10 does more than excluding undesired possibilities. It also enables us to give general statements about the structure of the class of adversarial divergences. The structural result can be easily stated under the notion of relative strength between adversarial divergences, which is defined as follows.

Let $\tau_{1}$ and $\tau_{2}$ be two adversarial divergences, if for any sequence of probability measures $(\mu_{n})$ and any target probability measure $\mu^{*}$, $\tau_{1}(\mu^{*}||\mu_{n})\to\inf_{\mu}\tau_{1}(\mu^{*}||\mu)$ implies $\tau_{2}(\mu^{*}||\mu_{n})\to\inf_{\mu}\tau_{2}(\mu^{*}||\mu)$, then we say $\tau_{1}$ is stronger than $\tau_{2}$ and $\tau_{2}$ is weaker than $\tau_{1}$. We say $\tau_{1}$ is equivalent to $\tau_{2}$ if $\tau_{1}$ is both stronger and weaker than $\tau_{2}$. We say $\tau_{1}$ is strictly stronger (strictly weaker) than $\tau_{2}$ if $\tau_{1}$ is stronger (weaker) than $\tau_{2}$ but not equivalent. We say $\tau_{1}$ and $\tau_{2}$ are not comparable if $\tau_{1}$ is neither stronger nor weaker than $\tau_{2}$.

Not much is known about the relative strength between different adversarial divergences. If the underlying sample space is nice (e.g., subset of Euclidean space), then the variational (GAN-style) formulation of $f$-divergences using bounded continuous functions coincides with the original definition , and therefore $f$-divergences are adversarial divergences. showed that the KL-divergence is stronger than the JS-divergence, which is equivalent to the total variation distance, which is strictly stronger than the Wasserstein-1 distance.

However, the novel fact is that we can reach the weakest strict adversarial divergence. Indeed, one implicatoin of Theorem 10 is that if $X$ is a compact metric space and $\tau$ is a strict adversarial divergence over $\tau$, then $\tau$-convergence implies the usual weak convergence on probability measures. In particular, since the Wasserstein distance metrizes weak convergence of probability distributions (see e.g. ), as a direct consequence of Theorem 10, the Wasserstein distance is in the equivalence class of the weakest strict adversarial divergences. In the other direction, there exists a trivial strict adversarial divergence

that is stronger than any other strict adversarial divergence. We now incorporate our convergence results with some previous results and get the following structural result.

The class of strict adversarial divergences over a bounded and closed subset of a Euclidean space has the structure as shown in Figure 1, where $\tau_{\!{}_{\text{Trivial}}}$ is defined as in (8), $\tau_{\!{}_{\text{MMD}}}$ is corresponding to example (c) in Section 3, $\tau_{\!{}_{\text{Wasserstein}}}$ is corresponding to example (d) in Section 3, and $\tau_{\!{}_{\text{KL}}}$, $\tau_{\!{}_{\text{Reverse-KL}}}$, $\tau_{\!{}_{\text{TV}}}$, $\tau_{\!{}_{\text{JS}}}$, $\tau_{\!{}_{\text{Hellinger}}}$ are corresponding to example (b) in Section 3 with $f(x)$ being $x\log(x)$, $-\log(x)$, $\frac{1}{2}\lvert x-1\rvert$, $-(x+1)\log(\frac{x+1}{2})+x\log(x)$, $(\sqrt{x}-1)^{2}$, respectively. Each rectangle in Figure 1 represents an equivalence class, inside of which are some examples. In particular, $\tau_{\!{}_{\text{Trivial}}}$ is in the equivalence class of the strongest strict adversarial divergences, while $\tau_{\!{}_{\text{MMD}}}$ and $\tau_{\!{}_{\text{Wasserstein}}}$ are in the equivalence class of the weakest strict adversarial divergences.

Related Work

There has been an explosion of work on GANs over the past couple of years; however, most of the work has been empirical in nature. A body of literature has looked at designing variants of GANs which use different objective functions. Examples include , which propose using the f-divergence between the target $\mu$ and the generated distribution $\nu$, and , which propose the MMD distance. Inspired by previous work, we identify a family of GAN-style objective functions in full generality and show general properties of the objective functions in this family.

There has also been some work on comparing different GAN-style objective functions in terms of their convergence properties, either in a GAN-related setting , or in a general IPM setting . Unlike these results, which look at the relationship between several specific strict adversarial divergences, our results apply to an entire class of GAN-style objective functions and establish their convergence properties. For example, shows that KL-divergnce, JS-divergence, total-variation distance are all stronger than the Wasserstein distance, while our results generalize this part of their result and says that any strict adversarial divergence is stronger than the Wasserstein distance and its equivalences. Furthermore, our results also apply to non-strict adversarial divergences.

That being said, it does not mean our results are a complete generalization of the previous convergence results such as . Our results do not provide any methods to compare two strict adversarial divergences if none of them is equivalent to the Wasserstein distance or the trivial divergence. In contrast, show that the KL-divergence is stronger than the JS-divergence, which is equivalent to the total variation distance, which is strictly stronger than the Wasserstein-1 distance.

Finally, there has been some additional theoretical literature on understanding GANs, which consider orthogonal aspects of the problem. address the question of whether we can achieve generalization bounds when training GANs. focus on optimizing the estimating power of kernel distances. study generalization bounds for MMD-GAN in terms of fat-shattering dimension.

Acknowledgments

We thank Iliya Tolstikhin, Sylvain Gelly, and Robert Williamson for helpful discussions. The work of KC and SL were partially supported by NSF under IIS 1617157.

References

Appendix A Proof of Theorem 4

We observe that the assumptions of the theorem imply that for any $\mu\in\mathcal{P}(X)$,

The assumptions also imply that for any $\mu,\nu\in\mathcal{P}(X)$,

Therefore $\mu\in\textsc{opt}_{\tau,\mu^{*}}$.

Appendix B Proof of Theorem 5

Since by Theorem 4 we already have $\mathcal{M}_{\mu^{*}}\subset\textsc{opt}_{\tau,\mu^{*}}$, we only need to prove for any $\mu^{*}\in\mathcal{P}(X)$,

where the last equality is due to (9). Finally note that

Therefore $\mu\not\in\textsc{opt}_{\tau,\mu^{*}}$. This concludes the proof.

Appendix C Proof of Corollary 6

Because $x_{0}$ is an interior point of $\operatorname*{dom}f^{*}$, we have $\theta^{\mu}_{\nu}$ is an interior point of $\Theta$, due to the compactness of $X$ and all $\psi_{i}$ being continuous and therefore bounded continuous. Also, it is easy to see that $r_{\theta^{\mu}_{\nu}}$ is a constant function.

Appendix D Proof of Theorem 10

We first need a standard result in functional analysis. A brief proof is provided for completeness.

If $X$ is a compact metric space, then $\mathcal{P}(X)$ is weak-* compact.

By the Banach-Alaoglu theorem, the following closed unit ball is weak-* compact.

Since the constant function $\mathbf{1}$ is in $C(X)$. The following set is weak-* closed.

which is weak-* closed. To justify the claim, on one hand, the l.h.s. is clearly a subset of the r.h.s.; on the other hand, to show the r.h.s. is also a subset of the l.h.s., consider a $\mu\in rca(X)$ with a Borel set $A$ such that $\mu(A)<0$ (i.e., $\mu$ is not in the l.h.s.), then by Lusin’s Theorem the measurable function $\mathbf{1}_{A}$ can be approximated by functions in $C(X)$ in the sense that for any $\epsilon>0$, there exists a $f_{\epsilon}\in C(X)$ such that

Since the intersection of a compact subset and a closed subset is a compact subset, we conclude that $\mathcal{P}(X)$ is weak-* compact. ∎

Now we can start the main proof. We equip $\mathcal{P}(X)$ with the weak-* topology. Let $\mu^{*}\in\mathcal{P}(X)$. Note that the function $\tau(\mu^{*}||\cdot)$ is the supremum of a family of affine continuous functions on $\mathcal{P}(X)$, therefore $\tau(\mu^{*}||\cdot)$ is lower semi-continuous on $\mathcal{P}(X)$. Note that by Lemma 13, $\mathcal{P}(X)$ is compact. Therefore by Weierstrass extreme value theorem, $\tau(\mu^{*}||\cdot)$ attains its minimual value on $\mathcal{P}(X)$, therefore $\textsc{opt}_{\tau,\mu^{*}}\neq\emptyset$.

Let $(\mu_{n})$ be a sequence in $\mathcal{P}(X)$. Assume $\tau(\mu^{*}||\mu_{n})\to\inf_{\mu^{\prime}}\tau(\mu^{*}||\mu^{\prime})$, we need to show that in the quotient space $\mathcal{Q}=\mathcal{P}(X)/\textsc{opt}_{\tau,\mu^{*}}$, $([\mu_{n}])$ converges to $\textsc{opt}_{\tau,\mu^{*}}$ . Let $\mathcal{N}$ be any open neighbourhood of $\textsc{opt}_{\tau,\mu^{*}}$ in $\mathcal{Q}$. We need to show that $([\mu_{n}])$ is eventually in $\mathcal{N}$.

First we show that $\mathcal{Q}\setminus\mathcal{N}$ is compact. By Lemma 13, $\mathcal{P}(X)$ is compact. Since $\mathcal{Q}$ is a quotient space of $\mathcal{P}(X)$, $\mathcal{Q}$ is compact. Observe that $\mathcal{Q}\setminus\mathcal{N}$ is a closed subset of $\mathcal{Q}$, therefore $\mathcal{Q}\setminus\mathcal{N}$ is compact.

Recall that $\tau(\mu^{*}||\cdot)$ is lower semi-continuous on $\mathcal{P}(X)$. Now observe that $\tau(\mu^{*}||\cdot)$ is also a function on $\mathcal{Q}$, and since $\mathcal{Q}$ is a quotient space of $\mathcal{P}(X)$, $\tau(\mu^{*}||\cdot)$ is also lower semi-continuous on $\mathcal{Q}$. By Weierstrass extreme value theorem, there exists $[\mu^{\prime}]\in\mathcal{Q}\setminus\mathcal{N}$ such that

Since $\textsc{opt}_{\tau,\mu^{*}}\not\in\mathcal{Q}\setminus\mathcal{N}$, we have $[\mu^{\prime}]\neq[\textsc{opt}_{\tau,\mu^{*}}]$. Therefore $\tau(\mu^{*}||[\mu^{\prime}])>\inf_{\mu}\tau(\mu^{*}||\mu)$. Recall that $\tau(\mu^{*}||[\mu_{n}])\to\inf_{\mu}\tau(\mu^{*}||\mu)$, $\tau(\mu^{*}||[\mu_{n}])$ will be eventually less than $\tau(\mu^{*}||[\mu^{\prime}])$. This means $([\mu_{n}])$ will eventually be in $\mathcal{N}$.

Appendix E Proof of Corollary 12

It is known that for nice spaces (e.g., bounded and closed subset of a Euclidean space), the variational (GAN-style) formulation of $f$-divergences using bounded continuous functions is equivalent to the original definition . Therefore we them interchangeably. already showed that total variation is equivalent to JS divergence and they are not equivalent to the Wasserstein distance. These two are also known to be equivalent to the squared Hellinger distance by noticing that

Both KL and Reverse-KL divergence are stronger than total variation by Pinsker’s inequality. They are in fact strictly stronger than total variation. Let $\mu^{*}=U(0,1)$, $\mu_{n}=U(1/n,1+1/n)$, where $U(a,b)$ is the uniform distribution on $(a,b)$. Note $\tau_{\!{}_{\text{KL}}}(\mu^{*}||\mu_{n})=\tau_{\!{}_{\text{Reverse-KL}}}(\mu^{*}||\mu_{n})=+\infty$ for any $n$ while $\tau_{\!{}_{\text{TV}}}(\mu^{*}||\mu_{n})\to 0$. We can also show they are not comparable with each other by considering $\mu_{n}=U(0,1-1/n)$ and $\mu_{n}=U(0,1+1/n)$ while $\mu^{*}$ is still $U(0,1)$. The same examples also show they are strictly weaker than the trivial divergence.

It is also known that $\tau_{\!{}_{\text{Wasserstein}}}$ and $\tau_{\!{}_{\text{MMD}}}$ metrize the weak-* topology of $\mathcal{P}(X)$ if $X$ is a compact metric space (see, e.g., ), therefore by Theorem 10 they are in the equivalence class of the weakest strict adversarial divergences.

It remains to show the trivial divergence is stronger than any strict adversarial divergence. Any sequence $\mu_{n}$ converging to $\mu^{*}$ under the trivial divergence is eventually $\mu^{*}$, therefore trivially converges under any other strict adversarial divergence.