Title: EVALUATING GANS VIA DUALITY

Abstract: Generative Adversarial Networks (GANs) have shown great results in accurately modeling complex distributions, but their training is known to be difficult due to instabilities caused by a challenging minimax optimization problem. This is especially troublesome given the lack of an evaluation metric that can reliably detect non-convergent behaviors. We leverage the notion of duality gap from game theory in order to propose a novel convergence metric for GANs that has low computational cost. We verify the validity of the proposed metric for various test scenarios commonly used in the literature.

1. INTRODUCTION:

In the past few years, generative models have become extremely popular in the machine learning community. This is largely due to the recent advances in the field of deep learning, which allowed deep neural generators to produce remarkable results for various tasks, including for example image generation (Radford et al., 2015) . Two notable approaches in this area are variational auto-encoders (VAEs) (Kingma & Welling, 2013; Rezende et al., 2014) , and generative adversarial networks (GAN) (Goodfellow et al., 2014) . In this paper, we focus on GANs, which are especially attractive as they circumvent the notoriously hard optimization of the data likelihood and instead use an adversarial game approach for training a generator.

Let us denote the data distribution by p data (x) and the model distribution by p u (x). A probabilistic discriminator is denoted by D v : x → [0; 1] and a generator by G u : z → x. The GAN objective is:

EQUATION

Each of the two players (generator/discriminator) tries to optimize their own objective, which is exactly balanced by the loss of the other player, thus yielding a two-player zero-sum minimax game.

Standard GAN approaches aim at finding a pure Nash Equilibrium by using traditional gradientbased techniques to minimize each players cost in an alternating fashion. However, the minimax objective of GANs makes the optimization process challenging. One of the central open issues is the non-convergence problem, which in practice leads to oscillations between different kinds of generated samples (Metz et al., 2016) . Many different techniques have been proposed to address the shortcomings of the original technique introduced by Goodfellow et al. (2014) .

Given the plethora of GAN-like approaches as well as different training methods, the community is now facing the problem of determining which approaches produce "better" generative models. This is in itself a challenging question as there is no clear evaluation criterion. In a recent large-scale empirical study, Lucic et al. (2018) showed that using various evaluation measures, many state-ofthe-art models are able to reach similar scores with enough tuning. In a recent survey, Borji (2018) discussed the merits of various evaluation metrics, pointing out that there is no clear consensus regarding which metric is the most appropriate to evaluate the quality of a generative model. While many metrics achieve reasonable discriminability (i.e. ability to distinguish generated samples from real ones), they also tend to have a high computational complexity. Many existing metrics are also specific to datasets of natural images, but we are also starting to notice the success of GANs in other fields such as in cosmology (Rodriguez et al., 2018) or in the medical domain (Schlegl et al., 2017) .

Another problem related to the evaluation of samples produced by a GAN is the lack of evaluation procedures to detect convergence. While various approaches have analyzed the convergence properties of alternating gradient-based techniques, most of them require the objective function to be convex-concave (Goodfellow et al., 2014; Nowozin et al., 2016) with the exception of Grnarova et al. (2018) who prove convergence for semi-concave zero-sum games. In general, alternating gradient descent can fail to converge (Salimans et al., 2016) . While this non-convergence behavior can in practice be visually recognized for some low-dimensional examples (such as a 2D mixture of Gaussian), this is in general more difficult in high-dimensional spaces due to the lack of a convergence metric. This has been pointed out before (see e.g. Mescheder et al. (2018) and (Fedus et al., 2018) who examine convergence on 2D problems and problems for which the true data distribution is known.

One of the common challenges that practitioners are facing is when to stop training. In particular, it is well known that the curves of the discriminator and generator losses oscillate (see Figures 12 and 13 ) and are non-informative as to whether the model is improving or not (Arjovsky et al., 2017) . This is especially troublesome when a GAN is trained on non-image data in which case one might not be able to use visual inspection or FID/Inception score as a proxy.

In this paper, our main contribution is to leverage existing ideas from game theory to propose a novel and computationally efficient convergence metric for GANs. The principle we follow is based on the theory of duality that was developed after Von Neumann (1928) derived the minimax theorem for zero-sum games. From duality, it follows that the minimax and maximin1 are dual to each other and strong duality holds for feasible problems. This duality also implicitly gives us a way to evaluate the deviation between minimax and maximin. As an example, let's consider a two-player game between the discriminator D and the generator G. The duality gap measures the difference between the values of the game under two scenarios: when D first commits to a strategy, and then G gets to respond; and when G commits first, and then D gets to respond. In this paper, we advocate the use of the duality gap as a measure of convergence for GANs and demonstrate its effectiveness for various settings commonly considered in the literature.

As a second contribution, we also demonstrate how to use the minimax loss value in order to detect mode collapse and measure sample quality. Unlike FID or the Inception score that require labelled data or a domain dependent classifier, our metric is domain independent and does not require labels.

Our experiments demonstrate that the duality gap and minimax loss are valuable tools to measure convergence and correlate well with existing evaluation metrics.

2. RELATED WORK:

Despite the impressive empirical performance achieved by the latest GAN models (Karras et al., 2017) , they are still subject to many unanswered questions. Among them is the issue of a fair evaluation procedure. Since the log-likelihood of the data is a common objective function to train a generative model, it would appear to be a sensible metric for GANs. However, its computation is often intractable and Theis et al. (2015) also demonstrate that it has severe limitations as it might yield low visual quality samples despite of a high likelihood. Perhaps the most popular evaluation metric for GANs is the inception score introduced by Salimans et al. (2016) that measures both diversity of the generated samples and discriminability. While diversity is measured as the entropy of the output distribution, the discriminability aspect requires a pretrained neural network to assign high scores to images close to training images. Various modifications of the inception score have been suggested. Gurumurthy et al. (2017) adds a term in the cost function to take into account diversity within samples in a particular class. Heusel et al. (2017) uses features from a hidden layer of the Inception Net, which are modelled as two multivariate Gaussians for the generated and true data. They then suggest using the Frechet Inception Distance (FID) between these two Gaussians to assess the quality of the samples. The authors demonstrate improvements over the inception score, especially more robustness to noise, as well as being able to detect intra-class mode dropping. Furthermore, they also demonstrate high degrees of consistency with human judgments.

Although this measure appears to have nice properties from an empirical point of view, the Gaussian assumption might not hold in practice. Furthermore, FID requires labelled data in order to train a classifier. Without labels, transfer learning is possible to datasets under limited conditions (i.e. the source and target distributions should not be too dissimilar).

Another popular metric introduced by Gretton et al. (2012) is the Maximum Mean Discrepancy (MMD) which measures the dissimilarity between p data and p u using independently drawn samples. It is a specific instance of an integral probability metric. A potential hurdle for MMD is that its computational complexity is quadratic in the sample size, although some linear approximation do exist (Gretton et al., 2012) . Finally, it also depends on the choice of the kernel.

There are many other metrics that have been suggested over the past few years. We refer the reader to Borji (2018) for a detailed survey. Perhaps the two approaches that are the most relevant to our approach are inspired by skill rating systems in games and were both introduced in Olsson et al. (2018) . The first method named tournament win rate considers a single model playing against past and future versions of itself. This measure is designed to monitor the progress of a single model as it learns during training. The second method named skill rating measures the aptitude of two different fully trained models. In some way, skill rating and tournament win rate can be seen as an approximation of the worst minimax value we advocate in this paper, where instead of doing a full-on optimization in order to find the best adversary for the fixed generator, the search space is limited to discriminators that are snapshots from training, or discriminators trained with different seeds.

We would like to conclude our discussion of related work by pointing out to the vast literature on duality used in the optimization community as a convergence criterion for min-max saddle point problem, see e.g. Nemirovski et al. (2009) ; Komodakis & Pesquet (2015) . Some recent work by Chen et al. ( 2018) also used duality in order to derive a Lagrangian objective to train GANs. Although we also make use of duality, there are some major differences that are worth pointing out. Unlike prior work, our contribution does not relate to optimising GANs, but instead in showing that the duality gap can be empirically used as a proxy to track convergence. We also demonstrate it can be computed at low cost.

3. DUALITY GAP AS A NATURAL PERFORMANCE MEASURE:

Standard learning tasks are often described as (stochastic) optimization problems; this applies to common Deep Learning scenarios as well as to classical tasks such as logistic and linear regression. This formulation gives rise to a natural performance measure, namely the test loss2 . In contrast, GANs are formulated as (stochastic) zero-sum games. Unfortunately, this fundamentally different formulation does not allow us to use the same performance metric. In this section, we describe a performance measure for GANs, which naturally arises from a game theoretic perspective.

We start this section with a brief overview of zero-sum games, including a description of the Duality gap metric and some of its properties. Then we illustrate the usefulness of this metric by analyzing the idealized setting where both G and D have unbounded capacity (this setting was previously discussed in Goodfellow et al. (2014) ).

A zero-sum game is defined by two players P 1 and P 2 who choose a decision from their respective decision sets K 1 and K 2 . A game objective M : K 1 × K 2 → R, sets the utilities of the players.

Concretely, upon choosing a pure strategy (u, v) ∈ K 1 × K 2 the utility of P 1 is -M (u, v), while the utility of P 2 is M (u, v). The goal of either P 1 /P 2 is to maximize their worst case utilities; thus, min

u∈K1 max v∈K2 M (u, v) (Goal of P 1 ), & max v∈K2 min u∈K1 M (u, v) (Goal of P 2 ) (2)

The above formulation raises the question of whether there exists a solution (u * , v * ) to which both players may jointly converge. The latter only occurs if there exists (u * , v * ) such that neither P 1 nor P 2 may increase their utility by unilateral deviation. Such a solution is called a pure equilibrium, and is formally defined as follows,

max v∈K2 M (u * , v) = min u∈K1 M (u, v * ) (Pure Equilibrium).

While a pure equilibrium does not always exist, the seminal work of Nash et al. (1950) shows that an extended notion of equilibrium always does. Specifically, there always exists a distribution D 1 over elements of K 1 , and a distribution D 2 over elements of K 2 , such that the following holds,

max v∈K2 E u∼D1 M (u, v) = min u∈K1 E v∼D2 M (u, v) (Mixed Nash Equilibrium).

Such a solution is called a Mixed Nash Equilibrium (MNE). This notion of equilibrium gives rise to the following natural performance measure of a given pure/mixed strategy. Definition 1 (Duality Gap). Let D 1 and D 2 be fixed distributions over elements from K 1 and K 2 respectively. Then the duality gap of (D 1 , D 2 ) is defined as follows,

EQUATION

Particularly, for a given pure strategy (u, v) ∈ K 1 × K 2 we define,

EQUATION

A well-known, straightforward property of the duality gap is that it is always non-negative. Moreover, by definition, the gap is exactly zero in (mixed) Nash Equilibrium solutions. This property is very appealing from a practical point of view, since it means that the duality gap gives us an immediate handle for measuring convergence.

Next we illustrate the usefulness of the duality gap metric by analyzing the ideal case where both the generator and discriminator have unbounded capacity. The latter basically means that the generator can represent any distribution, and the discriminator can represent any decision rule. The next proposition shows that in this case, as long as G is not equal to the true distribution then the duality gap is always positive. In particular we show that duality gap is at least as large as the Jensen-Shannon divergence between true and fake distributions (which is always non-negative). We also show that if G outputs the true distribution, then there exists a discriminator such that the duality gap is zero. Proposition 1. Consider the GAN game objective appearing in Equation ( 1), and assume that the generator and discriminator networks have unbounded capacity. Also, let (G, D) be a fixed solution. Then the duality gap of (G, D) is larger than the Jensen-Shannon divergence between the true distribution and the fake distribution generated by G. Moreover, if G outputs the true distribution, then there exists a discriminator D such that the Duality gap of (G, D) is zero.

4. ESTIMATING THE DUALITY GAP METRIC FOR GANS:

In this section we address several aspects of estimating the duality gap metric for GANs. First we discuss the appropriate way to estimate the metric using samples. We follow with advocating another metric that enables evaluation of a generator not necessarily trained by a GAN. Finally, we describe a method for an efficient and practical computation of the duality gap.

Appropriately estimating the duality gap from samples: Standard supervised learning problems are often formulated as stochastic optimization programs. Thus, we do not have direct access to the expected loss, but can instead estimate it through samples. In this case, it is well known that one should split the data into training and test sets3 . The training set is used to find a solution whose quality of the solution is estimated using a separate test set (which provides an unbiased estimate of the true expected loss).

Similarly, GANs are formulated as stochastic zero-sum games (Equation ( 1)). Nevertheless, in GANs the issue of evaluating the duality gap metric is more delicate. This is because we have three phases in the evaluation: (i) training a model (u, v), (ii) finding the worst case discriminator/generator, v worst ← arg max v∈K2 M (u, v), and u worst ← arg min u∈K1 M (u, v), and (iii) computing the duality gap by estimating: DG := M(u, v worst ) -M(u worst , v). Now since we do not have direct access to the expected game objective, one should use different samples for each of the three mentioned phases in order to maintain an unbiased estimate of the expected duality gap. Thus we split our dataset into three disjoint subsets, training set, adversary finding set, and test set which are respectively used in phases (i), (ii) ,and (iii).

Minimax Loss as a metric for evaluating generators. For all experiments we report both the duality gap (DG) and the minimax loss defined as M (u, v worst ). The minimax loss is the first term that contributes to the computation of DG and intuitively measures the 'goodness' of a generator G u . If G u is optimal and covers p data , the minimax loss achieves its optimal value as well. This happens when D vworst outputs 0.5 for both the real and generated samples. Whenever the generated distribution does not cover the entire support of p data or compromises the sample quality, this is detected by D vworst and hence, the minimax loss increases. This makes it a compelling metric for detecting mode collapse and evaluating sample quality. Note that in order to compute this metric one only needs a batch of generated samples, i.e. the generator can be used as a black-box. Hence, this metric is not limited to generators trained as part of a GAN, but can instead be used for any generator that can be sampled from.

Practical and efficient estimation of duality gap for GANs. In practice, the metrics are computed by optimizing a separate generator/discriminator using a gradient based algorithm. To speed up the optimization, we initialize the networks using the parameters of the adversary at the particular step we are evaluating. Hence, if we are evaluating the GAN at step t, we train v worst for u t and u worst for v t by using v t as a starting point for v worst and analogously, u t as a starting point for u worst for a number of fixed steps. 4 .

We also explored approximations of DG, where instead of using optimization to find the optimal v worst and u worst , we limit the search space to a set of discriminators and generators that are stored as snapshots throughout the training, similarly to (Olsson et al., 2018) (see results in Appendix B.3).

5. EXPERIMENTAL RESULTS:

Some notable desirable properties of a metric is that it should be able to efficiently (i) detect convergence and (ii) evaluate the quality of the generated samples. We carefully design a series of experiments to examine commonly encountered failure modes when training a GAN and analyze how this is reflected by the two metrics. Specifically, we show the sensitivity of the duality gap metric to (non-)convergence and the susceptibility of the minimax loss to reflect the sample quality.

Note that our goal here is not to provide a rigorous comparative analysis between different methods, but to demonstrate that both metrics capture desirable properties useful for training.

5.1. MIXTURE OF GAUSSIANS:

We train a vanilla GAN on three toy datasets with increasing difficulty, a) RING: a mixture of 8 Gaussians, b) SPIRAL: a mixture of 20 Gaussians and c) GRID: a mixture of 25 Gaussians. As the true data distribution is known, this setting allows for tracking of convergence and mode dropping.

Duality gap and convergence. Our first goal is to illustrate the connection between convergence and the duality gap. To that end, we analyze the progression of the duality gap throughout training in stable and unstable settings. One common problem of GANs is the unstable mode collapse, where the generator rotates between generating different modes. We simulate such instabilities and compare them against successful GANs in Table 1 . The gap goes to zero for all stable models after convergence to the true data distribution. Conversely, unstable training is reflected both in terms of the large value reached by the duality gap as well as its trend over iterations (e.g. oscillations indicate an unstable behavior). Thus the duality gap is a powerful tool for monitoring the training and detecting unstable collapse.

Minimax loss reflects sample quality. As previously argued, the duality gap achieves the lowest possible value of zero upon convergence to the NE. When DG = 0, the generated distribution, p u , equals the true data distribution, p data and there are no generated samples that lie outside of the support of p data . Whenever DG is not zero, another useful metric to look at is the minimax loss.

As this measures the loss given by the most adversarial discriminator, any mode collapse or lower sample quality can be detected by D vworst and hence lead to a larger minimax loss.

For the toy datasets, we measure the sample quality using (i) the number of covered modes and (ii) the number of generated samples that fall within 3 standard deviations of the modes. The correlation of these measures with the duality gap as well as with the minimax loss is reported in Figure 1 . We Figure 1 : DG, minimax, number of modes, and generated samples close to modes across epochs observe significant anti-correlation (especially for minimax loss), which indicates that both metrics capture changes in the number of modes and generated samples that lie outside of the support of p data , and hence the minimax loss can be used as a proxy to determining the overall sample quality. The previous experiment shows that unstable mode collapse is captured by DG. The trend of the curve is unstable and is typically within a high range. We are now interested in the case of stable mode collapse, where the model does converge, but only to a subset of the modes.

5.2. DG AND STABLE MODE COLLAPSE:

We train a GAN on MNIST where the generator collapses to generating from only one class (see Figure 2 ) (a-d) and does not change the mode as the number of training steps increases.

Figure 2 e) shows the DG curve throughout the training. The trend is flat and stable, but the value of the DG is not zero, thus showing that looking at the trend and value of the DG is helpful for detecting stable mode collapse as well. number of unique images within a class). For INC higher is better; for FID and minimax lower is better.

5.3. PROPERTIES OF THE METRIC:

We further analyze the sensitivity of the minimax loss to various changes in the sample quality for natural images that fall broadly in two categories: (i) mode sensitivity and (ii) visual sample quality.

Using images from Cifar10 we compare against the commonly used Inception Score (INC) and Frechet Inception Distance (FID). Both metrics use the generator as a black-box through sampling. We follow the same setup for the evaluation of the minimax loss. For the computation of the minimax loss we use the standard GAN zero-sum objective. Note that changing the objective to the WGAN formulation makes the minimax loss related to the Wasserstein critic (Arjovsky et al., 2017) .

Sensitivity to modes. The first set of experiments focuses on failures where the generated and ground truth modes do not fully overlap. As natural images are inherently multimodal, the generated distribution commonly ignores some of the true modes, which is a phenomenon known as mode dropping. We simulate mode dropping by using the class labels as modes. The metrics take as input a set of 5K images containing all 10 classes as 'real' images, and another set of 5K images composed of only subset of the modes (subset of 2, 4 and 8 classes) as 'generated' images (Figure 3 a ).

We then turn to mode invention where the generator creates non-existent modes. For this setting, the set of 'real' images contains only 5 classes, whereas the sets of 'generated' images are supersets of 5, 7 and 10 classes (Figure 3 b ). Intra-mode collapse is another common issue that occurs when the generator is generating from all modes, but there is no variety within a mode. The 'generated' sets consist of images from all 10 classes, but contain only 1, 50 and 500 unique images within a class.

Figure 3 shows the trends for all three metrics for the various degrees of mode dropping, invention and intra-class collapse. INC is unable to detect both intra-mode collapse and invented modes. On the other hand, both FID and minimax loss exhibit desirable sensitivity to various mode changing. Sample quality. We now undertake an analysis of the metrics' performance on distorted samples. We distort the real images using Gaussian noise, blur and swirl at an increasing intensity. As shown in Figure 5 , all metrics, including minimax, detect different degrees of visual sample quality.

Efficiency. A metric needs to be computationally efficient in order to be used in practice to both track the progress during training and as a final metric to rank various models. Figure 4 shows the wall clock time in terms of seconds for all three metrics. We keep the number of update steps fixed to 1K which makes the computation of the minimax loss efficient, as are the other two metrics. The computation of DG takes twice the time of the computation of the minimax loss.

We also test the variance across rounds due to randomness in the seed and how this affects the final metric and overall ranking, on a simple mode collapse task. Table 3 summarizes the average of 5 rounds showing that the variance is negligible and does not affect the effectiveness of the metric.

5.4. GENERALIZATION TO OTHER DOMAINS AND GAN LOSSES:

This experiment tests the ability of the two metrics to adapt to a different GAN loss formulation using the WGAN-GP objective (Gulrajani et al., 2017) , as well as other domains. In particular, we consider the field of observational cosmology that relies on computationally expensive simulations that produce images with very different statistics from natural images. In an attempt to reduce this burden, Rodriguez et al. (2018) trained a GAN to replace the traditional N-body simulators, relying on three statistics to assess the quality of the generated samples: the mass histrogram, the peak count and the power spectral density. As explained in Rodriguez et al. (2018) , these statistics are commonly used in cosmology to assess the quality of samples generated by N-body simulations. A random selection of real and generated samples shown in Figure 6 demonstrate the high visual quality achieved by the generator.

We evaluate the agreement between the statistics of the real and generated samples using the squared norm of the statistics differences (lower scores are therefore better). In Figure 7 , we show the evolution of the scores corresponding to the three statistics as well as the duality gap. We observe a strong correlation, especially between the peaks. Furthermore, it seems that the duality gap takes all the statistics into account. In Figure 8 , we plot the Pearson correlation between the duality gap, the minimax value and the scores. As explained in Rodriguez et al. (2018) , the distribution of the raw data is long-tail and has a very high dynamic range. Hence to simplify the learning process, the data is first mapped to [-1, 1] using a non-linear function. As a result, we additionally plot the same correlations for the raw data. From this experiment, we observe a strong empirical correlation between the duality gap, the minimax value and the cosmological scores. 

6. CONCLUSION:

The two proposed metrics complement other existing metrics and can be used by practitioners for monitoring progress towards convergence. While the minimax loss focuses on the performance of the generator (and the quality of its samples), the duality gap takes into account both the generator and discriminator. These metrics address two problems commonly faced by practitioners: 1) when should one stop training? and 2) if the training procedure has converged, have we reached the optimum or are we stuck in mode collapse? A significant advantage of the metrics is that, unlike many existing approaches, they require no labelled data and no domain specific classifier. Therefore, they are well-suited for applications of GANs other than the traditional generation task for images.

Of course, a downside is that -as most loss functions -the values obtained from these metrics are architecture and objective dependent, and can therefore not directly be compared. Yet, a practitioner can still rely on the overall trend throughout training for detecting non-convergent behaviors. Finally, one might want to use the generator as a black-box through its samples (this extends to other generative models too), in which case the minimax loss can be used as an evaluation metric directly.

A PROOF OF PROPOSITION 1:

Proof. To simplify notation, let us denote by p(x) the distribution over true samples and by q(x) the distribution over fake samples generated by G. Let us also denote the output of the discriminator by D(x). For simplicity, we will also slightly abuse notation and denote the GAN objective by M (q, D). Thus, the GAN objective reads as follows,

EQUATION

First we prove the first part of the proposition: Let us first recall the definition of the Jensen-Shannon divergence of two distributions p(•), q(•),

EQUATION

)

where the KL divergence is defined as,

KL(p || q) := p(x) log (p(x)/q(x)) dx .

Now given a fixed solution (q, D) we will show that the duality gap of this pair is bounded by the Jensen-Shannon divergence. It is well known that this divergence equals zero if both distributions are equal5 , and is otherwise strictly positive. To do so, we will first bound the minimax/maximin values for q/D.

(a) Upper Bounding Minimax Value: Given q(x), the worst case discriminator is obtained by taking the derivative of the objective in Equation ( 5) with respect to D(x) separately for every x (this can be done since we assume the capacity of D to be unbounded). This gives the following worst case discriminator (see similar derivation in Goodfellow et al. ( 2014)), D worst (x) := p(x) p(x) + q(x) .

Plugging the above value into Equation (5) gives the following minimax value,

EQUATION

(b) Lower Bounding Maximin Value: Here we lower bound the maximin value for a given q(x),

EQUATION

Maximizing the last expression separately for every x gives max

D(x)∈[0,1] 1 2 p(x) log D(x)dx + 1 2 p(x) log(1 -D(x))dx = -log 2

And plugging the above into Equation (8) gives,

EQUATION

(c) Upper bound on Duality Gap: Recall the definition of Duality gap,

DualGap(q, D) := max D M(q, D) -min q M(q, D) .

Using Equation ( 7) together with Equation ( 9) immediately shows that the duality gap is lower bounded by the Jensen-Shannon divergence between true and fake distributions. This concludes the first part of the proof.

Next we prove the second part of the proposition: Recall that we assume q(x) = p(x). And let us take, D(x) = 1/2, ∀x

Next we show that the Duality gap of (G, D) is zero.

(a) Let us first compute the minimax value: Similarly to Equation ( 7) the following can be shown,

EQUATION

)

where we used p(x)/(p(x) + q(x)) = 1/2.

(b) Let us now compute the maximin value. Since D(x) = 1/2 the following holds for any q 0 (x),

M (q 0 , D) = 1 2 p(x) log D(x)dx + 1 2 q 0 (x) log(1 -D(x))dx = -log 2 ,

which immediately implies,

EQUATION

)

Combining Equation ( 10) with Equation ( 11), with the definition of the Duality gap implies,

DualGap(q, D) = 0 .

which concludes the second part of the proof.

B EXPERIMENTS B.1 TOY DATASET: MIXTURE OF GAUSSIANS:

The toy datasets consist of a mixture of 8, 20 and 25 Gaussians for each of the models (RING, SPIRAL, GRID), respectfully. The standard deviation is set to 0.05 for all models except for the RING where the std is 0.01. Depending on the dataset, the means are spaced equally around a unit circle, a spiral or a grid.

The architecture of the generator consists of two fully connected layers (of size 128) and a linear projection to the dimensionality of the data (i.e. 2). The activation functions for the fully connected layers are relu. The discriminator is symmetric and hence, composed of two fully connected layers (of size 128) followed by a linear layer of size 1. The activation functions for the fully connected layers are relu, whereas the final layer uses sigmoid as an activation function.

Adam was used as an optimizer for both the discriminator and the generator with beta 1 = 0.5 and a batch size of 100. The latent dimensionality z is 100. The learning rates for the reported models are given as follows in Table 4 . The optimizer used for training the worst D/G is Adam and is set to the default parameters.

Plots of DG during training are given in Table 1 . Table 5 lists the obtained results for the methods in terms of their final duality gap, number of modes they have covered and the number of generated points that fall within three standard deviations of one of the means. The heatmaps of the final generated distributions are given in Figure 9 .

We also plot generated samples from the worst case generator in Figure 10 .

Progress during training for Figure 1 is given in Figure 11 . The generator and discriminator losses for our 2D ring problem are shown in Figure 13 . Based on the curves it is hard to determine when the model stops improving. As this is a 2D problem one can visually observe when the model has converged through the heatmaps of the generated samples (see Table 1 ). However in higher-dimensional problems (like the one discussed above on CIFAR10) one cannot do the same. Figure 14 The architecture of the generator consists of 5 fully connected layers of size 128 with leaky relu as an activation unit, followed by a projection layer with tanh activation. The discriminator consists of 2 dense layers of size 128 and a projection layer. The activation function used for the dense layers of the discriminator is leaky relu as well, while the final layer uses a sigmoid. The value α for leaky relu is set to 0.3.

The optimizer we use is Adam with default parameters for both the generator, discriminator, as well as the optimizers for training the worst generator and discriminator. The dimensionality of the latent space z is set to 100 and we use a batch size of 100 as well. We train for 10K steps. The number of steps for training the worst case generator/discriminator is 400.

We use the training, validation and test split of MNIST (Deng, 2012) for training the GAN, training the worst case generator/discriminator, and estimating the duality gap (as discussed in Section 4). 

B.2.2 MINIMAX EXPERIMENT ON CIFAR10:

Here we describe hyperaparameters for the experiment on Cifar10 (Krizhevsky et al., 2014) . The worst case discriminator we train is using the commonly used DCGAN architecture (Radford et al., 2015) . We again use Adam with the default parameters as the optimizer and the batch size is 100. We update the worst case classifier for 1K steps.

The hyperparameters used for the distortion in the experiment for visual sample quality are:

1. Gaussian noise Following the approach of Gulrajani et al. (2017) , we used a Wasserstein loss with a gradient penalty of 10. Both the generator and the discriminator were optimized with an "RMSprop" optimizer and a learning rate of 3 • 10 -5 . The discriminator was optimized 5 times more often than the generator.

B.3 APPROXIMATING THE DUALITY GAP:

We explored variants in which we are circumventing the optimization in order to find the worst case generator/discriminator by using a set of discriminators/generators out of which we choose the most adversarial one. The sets are created by saving snapshots of the parameters of the two networks during training. We explored variants where the snapshots come a) only from past models and b) a mix of previous and future models, and generally found b) to perform better. This setting is similar to the models proposed in (Olsson et al., 2018) , except they use skill rating systems to infer a latent variable for the successfulness of a generator. On the other hand, we compute the duality gap and the minimax loss to infer the successfulness of the entire GAN and of the generator, respectfully.

Table 6 gives the progression of the approximated duality gap for four various scenarios: stable model, unstable mode collapse and stable mode collapse. The duality gap was approximated using 10 models that spanned accross 2 epochs.

C ANALYSIS OF THE QUALITY OF THE EMPIRICAL DG:

The theoretical assumption appearing in the proof in Appendix A is that the discriminator and generator have unbounded capacity and we can obtain the true minimizer and maximizer when computing u worst and v worst , respectively. This, however, is not tractable in practice. Furthermore, it is well known that one common problem in GANs is mode collapse. This raises the question of how the duality gap metric would be affected if the worst generator that we compute is collapsed itself. In the following we address this both empirically and from a theoretical perspective.

We use the same experimental setup as described in Appendix B.1. We focus on a GAN that has converged such that the generator covers all modes uniformly i.e. p g = p data (Figure 15 a )). The discriminator outputs 0.5 for real and fake samples (Figure 15 b )). This means that the model has reached the equilibrium and the duality gap -in theory-is zero. Collapsed worst case generator. Now we focus on the calculation of the duality gap. Let us consider the case of a mode collapsed worst case generator. In particular, when computing the maximin part of the duality gap i.e. M (u worst,v ), let us assume the solution was such that G uworst only covers one mode of the true distribution (Figure 15 d )). Then M (u worst,v ) = log(0.5) + log(1 -0.5). The minmax calculation is: M (u, v worst ) = log(0.5) + log(1 -0.5). Hence, the value of DG is zero, despite the collapse in the calculation for the u worst . The generator has no incentive to spread its mass due to the objective. While this is a problem for the original GAN that is being trained, it is not an issue for the calculation of the duality gap metric.

Figure 16 b) shows samples generated from G uworst when the experiment is performed in practice.

We do observe that in this case, there is indeed a collapse that happened in the worst generator for the fixed GAN discriminator. Yet, D(G uworst ) = 0.489 and DG = 0.002 confirming the previous thought experiment. A heatmap with generated samples from the GAN generator are given in Figure 16 .

Hence, mode collapse for the computation of DG is not an issue. Note though that when there is mode collapse in the GAN itself that is being evaluated, the DG detects this. In particular, this is supported by the high anti-correlation between DG and the number of covered modes and sample quality as shown in Table 2 .

Suboptimal solutions due to the optimization. We now investigate the effect of the number of optimization steps used for the calculation of the duality gap on the quality of the solution. We run 5 different models with different hyperparameters with the goal to find the best setting. As suggested, we want to use the duality gap as the metric for this. Table 7 gives the results. The ranking of the models is the same for various numbers of optimization steps and corresponds to the ranking obtained by taking into consideration the number of covered modes and the number of generated samples that fall within 3 standard deviations of one of the modes. This suggests that as long as one uses the same number of optimization steps when comparing different models, the suboptimality of the solution is empirically not an issue. 

:

In game theory, the maximin value of a player is the highest value that the player is ensured to receive without knowing the actions of the other player(s) while the minimax value of a player is the smallest value that the other player(s) can force the player to receive, without knowing the player's actions.

For classification tasks using the zero-one test error is also very natural. Nevertheless, in regression tasks the test loss is often the only reasonable performance measure.

Of course, one should also use a validation set, but this is less important for our discussion here.

The code will be released upon acceptance.

We mean equal up to sets of measure zero.

Figures and Tables:

Figure 2: a-d: Generated samples at four different steps; e: DG through epochs

Figure 4: Wall clock time (in log-scale) for the calculation of INC, FID and minimax loss for increasing number of samples to be processed

Figure 6: Real and generated cosmological images representing slices of mass density of the universe. The yellow coefficient implies a high mass concentration

Figure 8: Correlation between cosmological scores DG

Figure 9: Heatmaps of the generated distributions at the final steps. On top: trained model (stable or unstable), on bottom: p data

showcases the progression of the duality gap throughout the training. Contrary to the discriminator/generator losses, this curve is meaningful and clearly shows the model has converged and when one can stop training, which coincides with what is shown on the heatmaps. B.2 OTHER HYPERPARAMETERS B.2.1 STABLE MODE COLLAPSE

Figure 11: Generated samples (blue) and real samples (green) throughout training steps

level 1: ksize = 2 (b) level 2: ksize = 5 (c) level 3: ksize = 7 3. Gaussian swirl with strength 5 (a) level 1: radius = 1 (b) level 2: radius = 2 (c) level 3: radius = 20 B.2.3 EXPERIMENT ON COSMOLOGY DATASET

Figure15: Analysis of a GAN that has reached the equilibrium for the mixture of 8 Gaussians problem. a) Samples generated from the GAN generator cover all 8 modes uniformly; b) Probabilities for a sample being real. The GAN discriminator assigns 0.5 probability to data points from the 8 modes and 0 everywhere else; c) For the computation of the duality gap, the theoretical v worst assigns 0.5 to fake/real samples for the fixed GAN generator; d) We assume there was mode collapse when computing u worst for the fixed GAN discriminator and samples from G uworst lie only on a single mode.

Progression of DG throughout training and heatmaps of the generator distribution

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">stable</td><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="2">unstable</td></tr><tr><td/><td/><td>15</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>RING</td><td>Duality gap</td><td>0 5 10</td><td colspan="2">0</td><td colspan="7">5000 10000 15000 20000 Steps</td><td/><td>Duality gap</td><td>12 13 14</td><td>0</td><td colspan="3">Steps 5000 10000 15000 20000</td></tr><tr><td/><td>step 0</td><td/><td/><td>step 3000</td><td>step 6000</td><td>step 9000</td><td>step 12000</td><td>step 15000</td><td>step 18000</td><td>step 21000</td><td/><td>step 24000</td><td>step 0</td><td/><td>step 3000</td><td>step 6000</td><td>step 9000</td><td>step 12000</td><td>step 15000</td><td>step 18000</td><td>step 21000</td><td>step 24000</td></tr><tr><td>SPIRAL</td><td>Duality gap</td><td colspan="2">0.0 0.5 1.0</td><td>0</td><td colspan="2">10000</td><td colspan="2">20000 Steps</td><td colspan="2">30000</td><td/><td/><td>Duality gap</td><td>0 5 10</td><td>0</td><td colspan="2">10000</td><td>20000 Steps</td><td>30000</td></tr><tr><td/><td colspan="2">step 0</td><td/><td>step 5000</td><td>step 10000</td><td/><td>step 15000</td><td>step 20000</td><td>step 25000</td><td>step 30000</td><td/><td>step 35000</td><td>step 0</td><td/><td>step 5000</td><td>step 10000</td><td>step 15000</td><td>step 20000</td><td>step 25000</td><td>step 30000</td><td>step 35000</td></tr><tr><td>GRID</td><td>Duality gap</td><td>5 10 15</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>Duality gap</td><td>12 13</td><td/><td/><td/></tr><tr><td/><td/><td>0</td><td colspan="2">0</td><td colspan="7">10000 20000 30000 40000 Steps</td><td/><td/><td/><td>0</td><td colspan="2">10000</td><td>20000 Steps</td><td>30000</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>step 0</td><td/><td>step 5000</td><td>step 10000</td><td>step 15000</td><td>step 20000</td><td>step 25000</td><td>step 30000</td><td>step 35000</td></tr><tr><td/><td>step 0</td><td/><td/><td>step 5000</td><td>step 10000</td><td>step 15000</td><td>step 20000</td><td>step 25000</td><td>step 30000</td><td>step 35000</td><td>step 40000</td><td>step 45000</td><td/><td/><td/><td/><td/></tr></table>

Pearson product-moment correlation coefficients for an average of 10 stable rounds.

Table content: <table><tr><td/><td>DG</td><td>Minimax</td></tr><tr><td/><td colspan="2">-0.63 -0.97</td><td>ring</td></tr><tr><td>Modes</td><td colspan="2">-0.59 -0.93</td><td>spiral</td></tr><tr><td/><td colspan="2">-0.71 -0.95</td><td>grid</td></tr><tr><td/><td colspan="2">-0.64 -0.94</td><td>ring</td></tr><tr><td>Std</td><td colspan="2">-0.64 -0.58</td><td>spiral</td></tr><tr><td/><td>-0.7</td><td>-0.93</td><td>grid</td></tr></table>

Metrics on a simple mode dropping task

Table content: <table><tr><td>Real samples 32x32</td><td>Fake samples 32x32</td></tr></table>

Learning rates used for the toy experiments.

Table content: <table><tr><td/><td/><td colspan="3">Duality Gap Modes Std</td></tr><tr><td/><td>RING</td><td>0.04</td><td>8</td><td>2375</td></tr><tr><td>stable</td><td colspan="2">SPIRAL 0.14</td><td>20</td><td>1999</td></tr><tr><td/><td>GRID</td><td>0.03</td><td>25</td><td>2370</td></tr><tr><td/><td>RING</td><td>13</td><td>2</td><td>152</td></tr><tr><td>unstable</td><td colspan="2">SPIRAL 1.22</td><td>1</td><td>1724</td></tr><tr><td/><td>GRID</td><td>12.09</td><td>3</td><td>37</td></tr></table>

Final results for DG, number of covered modes and number of generated samples (out of 2400) that fall within 3 standard deviations of the means.B.1.1 LOSS CURVESA common problem practitioners face is when to stop training, i.e. understanding whether the model is still improving or not. See for example Figure12, which shows the discriminator and generator losses during training of a DCGAN model on CIFAR10 (dcg). The training curves are oscillating and hence are very non-intuitive. A practitioner needs to most often rely on visual inspection or some performance metric as a proxy as a stopping criteria.

Table content: <table/>

Progression of DG throughout training and heatmaps of the generator distribution. A1: stable ring, A2: unstable ring, B1: mode collapse, B2: stable mode collapse

Table content: <table><tr><td/><td/><td/><td/><td>1</td><td/><td/><td/><td/><td/><td/><td/><td/><td>2</td><td/><td/><td/><td/></tr><tr><td>A</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>step 0</td><td>step 1000</td><td>step 2000</td><td>step 3000</td><td>step 4000</td><td>step 5000</td><td>step 6000</td><td>step 7000</td><td>step 8000</td></tr><tr><td>B</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>step 0</td><td>step 1000</td><td>step 2000</td><td>step 3000</td><td>step 4000</td><td>step 5000</td><td>step 6000</td><td>step 7000</td><td>step 8000</td><td>step 0</td><td>step 1000</td><td>step 2000</td><td>step 3000</td><td>step 4000</td><td>step 5000</td><td>step 6000</td><td>step 7000</td><td>step 8000</td></tr></table>

Peer review (iclr2019):
 The focus of the submission is GANs (generative adversarial network), a recent and popular min-max generative modelling approach. Training GANs is considered to be a challenging problem due to the min-max nature of the task. The authors propose two duality-inspired stopping criteria to monitor the efficiency and convergence of GAN learning. Though training GAN can have some useful applications, the contribution of the submission is pretty moderate. i) Duality-inspired approaches, embedded also in optimization have already been proposed: see for example *Xu Chen, Jiang Wang, Hao Ge. Training Generative Adversarial Networks via Primal-Dual Subgradient Methods: A Lagrangian Perspective on GAN. ICLR-2018.*. ii) The notion of generator and discriminator networks with unbounded capacity (which is an assumption in *Proposition 1*) lacks formal definition. I looked up the cited Goodfellow et al. (2014) work; it similarly does not define the concept. Based on the informal definition it is not clear whether they exist or are computationally tractable. Minor comments: -MMD is a specific instance of integral probability metrics when in the latter the function space is chosen to be the unit ball of a reproducing kernel Hilbert space; they are not synonyms. -mixed Nash equilibrium: E_{v.sim D_1} should be E_{v.sim D_2}. -It might be better to call Table 1 as Figure 1. -References: abbreviations and names should be capitalized (e.g., gan, mnist, wasserstein, nash, cifar). Lucic et al. (2017) has been accepted to NIPS-2018.