Instability and Local Minima in GAN Training with Kernel Discriminators
Authors: Evan Becker
Parthe Pandit
Sundeep Rangan
Alyson Fletcher
Venue: NeurIPS 2022 Accept (2022)
Keywords: GANs
stability
kernel
linearization

Abstract: Generative Adversarial Networks (GANs) are a widely-used tool for generative modeling of complex data.  Despite their empirical success, the training of GANs is not fully understood due to the joint training of the generator and discriminator. This paper analyzes these joint dynamics when the true samples, as well as the generated samples, are discrete, finite sets, and the discriminator is kernel-based. A simple yet expressive framework for analyzing training called the $\textit{Isolated Points Model}$ is introduced. In the proposed model, the distance between true samples greatly exceeds the kernel width so that each generated point is influenced by at most one true point. The model enables precise characterization of the conditions for convergence both to good and bad minima. In particular, the analysis explains two common failure modes: (i) an approximate mode collapse and (ii) divergence. Numerical simulations are provided that predictably replicate these behaviors.

Instability and Local Minima in GAN Training with Kernel Discriminators
Evan Becker
Parthe Pandit HDSI
Sundeep Rangan Dept. ECE NYU
Dept. CS UCLA
UC, San Diego
evbecker@cs ucla.edu
par wwthheannittuussseee edu
sranganênyu.edi
Alyson K. Fletcher
Dept. Statistics UCLA akfletcherOuclaa.ddi
Abstract
Generative Adversarial Networks (GANs) are a widely-used tool for generative modeling complex data. Despite their empirical success, the training GANs is not fully understood due to the min-max optimization of the generator and discriminator. This paper analyzes these joint dynamics when the true samples well as the generated samples are discrete, finite sets, and the discriminator is kernel-based. simple yet expressive framework for analyzing training called the !solated Points Model is introduced. In the proposed model, the distance between true samples greatly exceeds the kernel width, so each generated point is influenced by at most one true point. Our model enables precise characterization the conditions for convergence, both to good and bad minima. In particular, the analysis explains two common failure modes: (i) approximate mode collapse and (ii) divergence. Numerical simulations are provided that predictably replicate these behaviors.
Introduction
Generative Adversarial Networks (GANs) are the most widely-used method for learning generative models of complex and structured data in unsupervised manner. Indeed, GANs have seen incredible empirical success a wide variety of domains ranging from image generation, speech generation, text generation, and many more. Models trained in this manner have also become critical in downstream applications. See [1,29] for an overview.
In the GAN methodology, generator model is trained to output samples that emulate a target dataset, which we call true samples. critic model, called the discriminator, is trained tell apart (discriminate) the true and generated samples. The generator is trained in parallel to fool the discriminator.
Correctly tuning the joint training of the discriminator and generator is one of the key challenges in GANs and is the source of several empirically observed problematic phenomena. For example, is well-known that the resulting distributions can suffer from mode collapse and catastrophic forgetting. The optimization can also lead divergence or slow convergence of min-max optimization algorithms. See [10, 19] for more details. Practical GANs methods overcome these issues with combination of careful haper-parameter optimization and heuristics. Significant effort has strived to develop theoretical frameworks that can better analyze and optimize GAN training.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

V
V/2
P1 0.125
P2 0.25
A = 0
A -..25
Diverging
V/
V4
P3 0.375
P4 0.25
A3 0.125
A4 0.25
Figure 1: (Isolated Points Model) An illustration of our results. Each isolated region (blue circle) has single true point (green disk) with point mass p;- There eight generated points with fixed point mass P3 = 1/8 starting at the locations shown in the orange squares. In V1 and V3, the excess point mass is non-negative (A; 2 0) and the generated points converge to the true point. In V2, the excess point mass A4 < 0 and the generated points converge to stable equilibrium around the true point analogous of mode collapse. Finally, a point outside all four isolated regions may diverge oo in linear velocity.
In this work, we propose simple theoretical model, called the Isolated Points Model, that is analytically tractable and allows us rigorously study the stability and convergence properties of training a GAN. In the proposed model, the true and generated points are discrete distributions over finite sets, and the discriminator is kernel-based meaning that it is linearly parametrized. We make an additional critical assumption that the true points are sufficiently separated such that the kernel interaction between points near two distinct true points is negligible. For distance-based kernels, this assumption essentially requires that the true points are separated much greater than the kernel width. simple example of this model with four true points illustrated Fig.
Main Contributions We show that this simple isolated points model provides sufficient richness to exhibit several interesting phenomena and insights:
(1) Local stability and instability: We provide necessary and sufficient conditions for local conver- gence of generated points to a true point within each isolated region (Theorem I). The results show that the stability determined by the excess point mass, meaning the difference between the true and generated mass in the region. A consequence of these results, Corollary 1, is that exact mode collapse where an excess generated points concentrate single true point, provably not possible.
(2) Approximate mode collapse: Although an excess of generated point mass cannot exactly concen- trate on single true point, we prove (see Theorem 2) the existence locally stable equilibria where an arbitrarily large excess point mass concentrates near the true point. We call this phenomena approximate mode collapse.
(3) Divergence: We also demonstrate that given initial perturbation, an isolated generated point can lock into an trajectory moving away from any true point in an arbitrary direction. Interestingly, this trajectory driven solely by the generated point's own kernel history.
(4) Role of the kernel width: The results provide insights into the role of the kernel width in training See Section 6. In particular, wider kernel widths reduce the likelihood of different modes of the distribution being isolated, which is the critical for the approximate mode collapse and divergence that we observe. At the same time, discriminators with wide kernels make are unable distinguish points that are close, resulting in slow convergence near the true distribution.

---

Prior work Convergence problems for GANs have been widely-recognin and studied since their inception [1. Indeed, many of the developments GANs, notably the popular Wasserstein GAN and its variants, were motivated to overcome these issues 1,,3, 13, 17].
For analytic tractability, maximum mean discrepancy loss. This methodology has been applied in other works such as 16,9,12,27]. Our focus is on joint optimization a kernel discriminator and generator with multiple discrete points, An important avenue of future work would be to extend our results to more complex losses such as the Wasserstein loss 12,3,33]
focus
relatively simple GAN with kernel diseriminator and
The early Dirac-GAN [19], and its extension [26], considered a linear discriminator and a single strac-distribution for the generator and true data. Our model extends this work by considering multiple points and a general kernel discriminator. Importantly our model allows for new parameter called the excess point mass which enables modeling complex behaviours in the isolated regions.
Our results also heavily rely on linearization methods derived from control theory, which have been studied in the GAN context in [21,22,30] See, also general functional descriptions in [9, 2,,20,22 23]. These prior works demonstrated the local stability of the generated distribution close to the true distribution. Stability results with a single-layer NN generator and linear discriminator has been studied in [4]. Due to the isolated points model, our results also prove the existence of locally stable bad local minima.
Metrics for understanding the performance of generative models remains an open challenge. Some efforts in this direction were presented in [8, (8,, and we take advantage of this progress to report our numerical simulations.
2 Isolated Points Model
We propose the following model for studying the training of GANs.
Discrete true and generated distributions: We assume that the true and generated distributions, F. and P. 9, are over discrete sets in R
N Σ pro(a mx), Pa(x)) Σ pjo(a Tz))
P. (xx
where N, and N, are the number of true and generated points, X ( and x are the true and generated points, respectively, and {p.} and {p,} are their probabilities. For the generator, we assume that the probabilities p5 are fixed. The problem is to learn the point mass locations X that the generated and true distributions match.
Kernel discriminator: We consider a GAN where the discriminator has a linear parametrization of the form:
f(x = TO
for some vector of basis functions a(x) and parameter vector 0. The discriminator is trained to maximize a maximum mean discrepancy (MMD) metric [6,9, 12,27]
X
La (T,))²)
Σ pa]( 0) - Σ P 0)
1012
(3)
2
for some regularization parameter À > 0.
Diseriminator updates:
We assume simple gradient ascent of the MMD metric (3):
gk+1 @h + na Σ p:a(x;)) - ()((t))) -10+)
10t )00)
(4)
3
3

---

where > 0 is the discriminator step-size. If we let (*(x) == f(x, then for any fixed æ, we have (x+ (x) + md
- - -
(5)
where K(x, x²) is the kernel:
(xx x') == a(x))Ta(x')
(6)
To make the analysis concrete, some of results will apply to the radial basis function (RBF) kernel
(1x x') = 2 1|m-2111
where a > is the kernel width.
Generator updates: We will assume the generator distribution P. in (1) is directly parameterized
by the point mass locations, X = { that are updated to minimize the loss:
0, (1 = "f,
(8)
We consider simple gradient descent update for this loss
3 + = .. MgP (
(9)
Together, (5) and (9) define the joint dynamics the GAN.
Isolated Points: Our final key assumption is that the true samples are separated far enough so that there exists non-empty isolated neighborhood V, around each sample æ; such that,
K (xx x') = 0 for all a E V; and x' E V3 for all +
(10)
In other words, the samples are separated sufficiently far apart such that they outside the width of the kernel evaluated at another sample. See Figure for an illustration.
The assumption (10) is obviously strict and is an idealization of what occurs in practice. The supplementary material discusses modifications of the results the case where [K(x, x²) c for some small and all V, and x' E Vj-
Now consider an isolated region V, around a true point T,, At each training step k. let N be the set of indices j such that the generated points ã V,, We further suppose that N is constant over time, so the points E do not enter or exit this region. Then, their dynamics within the region are given by:
p = (xx) + xx)
Σ (,K(z, (x
{f((z)
Vo E Vi,
(11a)
JEN,
= nopp V
bj E N
(11b)
We will call the updates (11) the dynamical system in the region V,,
We may also choose write the updates (11) in terms of the components of 0. Let 0, P.O where P. is the projection onto the range space of a(x) for æ E V,. Then, can be verified that the updates in (1 can be written as:
gh++1
0
+ Tl
pia(x,)
Σ p)a( xx)()))
(12a)
JEN:
b+1
+
no
0;), VjEN,
(12b)
We will use the notation
X, - j N
(13)
to denote the set of generated points TG in the isolated region. The state variables for the dynamics (12) can be represented by the pair (0., X,). Note that we allow separate learning rates for the two update equations. Our convergence result in Theorem I rely on the ratio of these learning rates.

---

3 Behavior Near the True Point
Consider isolated region Vi around some true point a;. We first analyze the dynamics where
T R xz Vj E Ni.
(14)
That is, all the generated points in V; are close to the true point. We follow a standard linearization analysis used in several other GAN works such [6, 12, 18J. However, critical difference in our model is that the generated mass may not equal the true mass in a particular isolated region. We thus define the probability mass difference
A Σ P
(15)
JEN,
which represents the difference the true probability mass in the region, pi, and total probability mass of the generated points in that region. Note that this parameter is missing from the analysis of Dirac-GAN [20] since A, = trivially when only one true point exists. Several numerical behaviors of GANs emerge due to A; o 0.
Assumption 1. The kernel K (ax,, x²) is smooth and, at each true point m;:
OK (K(x, a:a)
0,
(16)
Ox
==
and
8 K (ar, ar))
8 K (Kxxa') Oxdxx
[R1,, I,
E [Na, Ka I
(17)
Ox?2
In m2.
I mm ma
for some k1, k2, k3, K4 where we use the notation that E [q) 42] to mean q 1 Q 3 92
The condition mild and simply requires that the kernel K(xx, æx) has a local maxima = 3;; with negative curvature, and also satisfies strict positivity condition. The assumption, for example, satisfied by the RBF kernel (7) with k = k2 = K3 = K4 = 1/o².
Theorem 1. Fix any isolated region V,, suppose the kernel satisfies Assumption I and let
X
15 jE N.),
=
(18)
Then, there is unique 0 such that (0 X is an equilibrium point of the GAN dynamics (12) in the region V. In addition, if the parameters kú and μ ng/ na are fixed, then, for sufficiently small step size na:
(a) If A O, the equilibrium point is locally stable
(b) If A < and [N.] 2 1, the equilibrium point is locally unstable.
(c) If N = and
pAchii + min (X2,1pkka] > O,
(19)
the equilibrium point is locally stable.
(d) If [. and
pAckopi + min (D2,uptka} < O.
(20)
the equilibrium point is locally unstable.
In cases (c) and (d), 5ı denotes the point mass of the single generated point in region.
The thcorem provides simple necessary and sufficient conditions on the stability of equilibrium points at the true point. In case (a), we that when the probability mass difference, A, > O, the generated points will converge locally to the true point. That is, the generated points will converge to the true point as long the the true point mass exceeds the total generated mass. Also, (19) will always be satisfied when A = O. So, when N = (i.e., there is a single generated point), the generated point will converge to the true point when the generated and true point have the same mass. Examples of these convergence situations are shown in Figure 1, in V, (where A = 0) and Va (where A3 > 0).
Conversely, case (b) shows that when A, < O (i.e. the generated probability exceeds the true probability), the generated mass can no longer stably settle in the true point. This case is shown in V/2 in Fig. where the generated points repelled from the true points.
5

---

Single vs. multiple points: Note there is slight difference between the cases when |N,] 1 (i.e., there is single generated point in the region), and [[V 1, when there is more than one generated point. As the proof of the theorem shows, when [N,] > 1, the mean of the generated points may converge to the true point, but the system may have other modes that are unstable in other directions.
Boundary cases: Our theorem does not discuss certain boundary cases, For example, when A, = 0 and |N 1, the theorem does not state whether the equilibrium point is stable or unstable. These boundary cases are standard in linearization analyses when the eigenvalues of the linearized system are only critically stable. Critically stable linear systems will have limit cycles [28]. The stability of general nonlinear systems will be determined by the higher order dynamics, which, in our case, would be determined by the higher order terms of the kernel. However, standard non-linear systems theory results such as [28] show that any such points cannot be exponentially stable. Hence, if the points locally converge, the convergence rate may be slow.
Relation to Dirac-GAN: Note that our theorem recovers the stability result [20, Theorem 4.1] as a special case: When there is single true and generated point (whereby |.Ng = 1 and A, = 0), and regularization is used (A > 0), the theorem shows the true point is locally stable. When there is no regularization (A = 0). the criteria in both (19) and (20) are both exactly zero, mcaning the equilibrium point is not exponentially stable or unstable. In this case, [20] shows that the system has a limit cycle.
Non-existence of exact mode collapse: An important corollary of these results is provided by the following result.
Corollary Suppose the kernel satisfies Assumption 1, and the number of true and generated points are equal so that N, = Ng = N for some N. Also, suppose that Pj P3 = 1/N for all j. Then, the only stable equilibrium of the generated distribution Pg with
supp(1p,) S ssupp(P,,)
(21)
Pg P,,
In Corollary 1, supp(-) denotes the support of the distributions. So, supp(F",) denotes the set of non-unique values of true points æ; and and supp(IP,) denotes the of non-unique values of generated points ē.. Thus, the result rules out the possibility that the generated distribution can find a locally stable equilibrium where multiple generated points converge to a single true point.
4 Bad Local Minima and Approximate Mode Collapse
Mode collapse is one of the most videly-known failure mechanisms of GANs, especially for the simple GANs considered in this work 11, 19. Corollary 1 appears to rule out mode collapse in the sense that there are no locally stable equilibria where multiple generated point arrive in single true point. Indeed, Theorem suggests that the generated points will be "repelled" from the true point when the generated mass exceeds the true mass, i.e., A, < O. This repulsive force offers the possibility that the excess generated mass can move towards other true points.
However, in this section, we will show that even when A; < O, the generated points may get stuck close to the true point. This phenomena is what we call approximate mode collapse.
Theorem 2. Fix region V; and consider the dynamical system (12) with the RBF kernel (7). Assume [N.] > 1 so there more than one generated point in the region. Then, there exists a constant c > O, independent of the kernel width a, and N Nuazo which is only finction of d, such that, if [N S Niaxx the system has a locally stable equilibrium with X
{ E Ni) and
x; S co,
(22)
for all j E No.
The theorem states that, under certain conditions, the generated points can get stuck a local minima, even when the generated mass exceeds the true mass. An example of this situation is illustrated in Figure 1 in the region V2. The true mass (the green disk at the center of V2) is itself an unstable location for the generated points since A < O. But, the points may find stable local minima around

---

the true point. Moreover, the distance of the local minima to the scales with the kernel width Hence, for very small o, the generated points with arbitrarily high mass may accumulate near single true point. This phenomena can thus be seen as a type of approximate mode collapse.
The proof of Theorem 2 shows that the had minima holds for kernels other than the RBF well.
Prior work in mode collapse have identified at least two failure mechanisms: The first is that the discriminator may have zero gradient on the generated data when it comes from low dimensional manifold [2]. The above result provides a constructive proof for the existence such modes, and additionally shows that the local minima is stable, meaning the gradients push the generated data locally to the bad minima.
A second failure mechanism is catastrophic forgetring [26], that past generated values are not remembered by the discriminator. Since we use regularized discriminator (A > 0), our discriminator also "forgets" past values, and thus, the existence of the bad minima would be consistent with catastrophic forgetting.
Divergence
What happens to generated points isolated from all the true points {m:}? Consider single generated point To whose trajectory { x20 satisfies
K k -5}) = Vj 00
K K k x.,) = Vi
for all k.
(23)
That is, 2 is sufficiently far from all the other generated points and true points so that the kernel can be treated as zero. In this case, the dynamics (5) and (9) reduce to
(x) = (1 (x) K(x, z:p)) ) k+1 a + ng V ( (2b+1).
(24a)
(24b)
Theorem 3. Consider the dynamical system (24) with translation-invarian kernel of the form K(x,, x²) <[1= æ'I)) for some smooth, integrable function x(-) with <(0) > 0. Then, for any initial condition, T. and unit vector u E Rd, and X sufficiently small, there exists an initial discriminator function (xx and velocity vo 0 such that the solution the system in equation (24)
kuyu.
(25)
Remarkably, the theorem shows that an isolated generated point can enter a trajectory where continues to move linearly in direction simply propelled by its own kernel history K (æ, z()). This situation illustrated in Figure where the generated point in the top right moves to the right in a straight line. We will see several examples of divergence in the numerical results as well.
6 Role of the Kernel Width
key parameter of any distance based kernels, such as the RBF (7), its kernel width, meaning the approximate distance at which the kernel begins to decay significantly. Our results, combined with previous analyses, provide useful insights into the role of the kernel width GAN training.
For example, consider the simple case of the Dirac-GAN where there a single true point Dg and single generated point Eg. If we fix the generated point, To. and let an RBF discriminator run the convergence, it is known from results in [6, 12, 18] that the discriminator parameters 0* will converge some values 0* 0*, and the resulting generator loss in (8) is given by
C xo) 1 (1 (1- -1-e- Iz0- Peo-ãoh #oll /200
(26)
The supplementary material reviews these results in a more general setting.
Now, if the kernel width a is very large, the loss will have a small gradient when Ty is close to Wo i.e., the generated point close to the true value. On other hand, if a is very small, the loss will have small gradient when To is far from Zg. The selection of the appropriate o must balance the convergence rates in these two regimes. addition, when a is large, the discriminator approximately linear and therefore cannot distinguish nonlinear regions.
7

---

width=0.1 0.1
width 0.15
width= 0.2
-1
-1
-1
-2-2
11
w.
width=0.4
width=0.6
2
1
0
-1
=1
-1
-2
-2
-1
2
-1
0
w.
width=1.6
width=3.2
2
2
1-
-11
-1
1
-1
-2 0
- -1
2
-1 0
Figure 2: Behavior of joint GAN training with kernel width: Example trajectories generated points the course of training (red lines with final point marked cross), true distribution (green), final discriminator (blue and yellow colormap).
The results for the isolated points model provide additional insight. The isolated points assumption arises when the true points become separated at distance much greater than a. In such cases, have seen that least two failure modes become possible: (1) approximate mode collapse, as described in Theorem 2: and (2) divergence, as described in Theorem 3, where generated points isolated from all true points diverge in arbitrary directions. These two failure mechanisms may be prevented with wider kernel width to preclude the isolated points assumption. However, wide kernel widths come the price of poor discriminator power and slow convergence near the true point.
7 Numerical Examples
We conduct a simple experiment on low-dimensional, synthetic data to illustrate the behavior that the theory predicts. We also look at the frequency of GAN failure modes function of kernel width of the discriminator. Our main observation that failure most often occurs when the model is in an isolated points regime at small kernel width.
Two simple datasets for the unit circle in dimension d = 2; and set of N, = 10 points randomly distributed on the unit sphere dimension d 10. both cases, we initialize Ng = N, generated point as Gaussians with zero mean and E. | 2 1. We approximate the RBF discriminator using random Fourier feature map as in [24]. We set À = 0.01 and nl flg 10-3 and use 40000 training steps. Other details are in the Supplementary material.
data are used: A of N, points arranged uniformly on the
Figure 2 show example trajectories for the = 2 case for different kernel widths a. For the two dimensional setting we visualize the trajectories of generated points over the course of training in Figure 2. We see diverging behavior at very small kernel widths, as these generated points are not influenced by the kernels of the true points. Instead they "wander" off. Although Theorem shows linear diverging trajectories, other diverging trajectories may be possible due to the randomness

---

10, the frequency of divergence is small for de diverged per trial
d-2
0.3
d-2
W2 distance
d=10
d=10
initial
0.2
3-
0.1
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
kernel width
kernel width
(a) Normalized Wasserstein distance
(b) Frequency of divergence
Figure 3: Frequency of different GAN failure modes in four point, two dimensional setting and 10 point, 10 dimensional setting. (a) The median change in Wasserstein distance between true and generated distributions after 40k iterations. Different kernel widths an RBF kernel discriminator are tested. (b) The average percentage of diverging generated points after training GAN with RBF kernel discriminator. A generated point is considered diverging x > 2
in Fourier feature map. Also, in the example at 0.6, we see an approximate mode collapse where two generated points converge to single true point. Finally, at very large kernel widths the discriminator is not able to properly distinguish between distributions, and as result we see large oscillations. The discriminator gradients are much smoother, meaning they are closer to the linear diseriminator regime from the original Dirac-GAN analysis [19,
To measure how these failure mechanisms affect the overall performance, for each kernel width σr we run 100 trials of the true and generated points. Figure 3 plots the median performance of the GAN along two metrics. In Figure 3(a), we measure the Wasserstein-2 distance [14] between true and generated distributions before and after training period for fixed number of iterations. The Wasserstein-2 distance is estimated by [7] and provides еrror due to diverging points and mode collapse. We see that very low kernel widths, the normalized error can be even greater than one, meaning that the generated points are further from the true points than their initial value. This behavior is a result the divergence. At very high kernel widths, there is also significant error due to the slow convergence and lack of power of the discriminator.
As simple measure of frequency of divergence, Figure 3b measures the average fraction of generated points, j. where | > 2 at the end of the iterations. Since the true points are on the unit sphere [|<=:|| 1), this condition can be considered significantly from all the true points. As expected, we see that the frequency of divergence increases with small kernel width. However, for dimension very low kernel widths. This phenomena is result of the fact that we are approximating the RBF with random features. As shown [24], the number of features required for a good approximation to the RBF grows with d?.
case where the generated points have move
Potential Solutions via Multi-Scale Kernels
The above discussion and simulations shows that there is fundamental trade-off with respect to the kernel width. On the one hand, very wide kernels tend to provide slow rates convergence. In addition, they not able accurately discriminate between true points that are close. On the other hand, very narrow width kernels can result in true points being isolated from one another. The results in this paper show that isolated points lead both approximate mode collapse and divergence of generated points far away from the true distribution. Fortunately, the analysis in the paper suggests a way to avoid both of these conditions. Specifically, suppose consider kernel where the discriminator is of the form:
f(x, 01,0,) aj (2) + az(x)T(2,
(27)
where (3r) and (2) are two basis functions and 0 (0,, 02) are the parameters. The kernel for this discriminator
K(2,x') K1 x') K2(x,x'),
(28)

---

101
12 distancc (log) to true point
Figure 4: GAN training dynamics us- ing fixed-width kernel discriminators (blue, yellow, and green dashed lines) compared to the GAN training dynam- ics using feature map constructed by concatenation fixed-width fea- ture maps (illustrated by solid line). A concatenated feature map produces kemnll that is linear combination of its component kernels
10-1
mihh-11
10-3
wdthw1
with-10
muliocate jo 1,030
5300
10300
12500
15030 17520
20000
training Iteration
where K2(z, x²) = (x(=)),((a")) are the kernels for each of the bases.
Now, suppose that a1 (ar) and (2)))) are selected so that K1 has a wide width and K2(x) has a small width. We call such a kernel multi-scale. The overall kernel (28) will have heavy tail component due to the "wide" kernel (x).. Hence, it can avoid the isolated points problem. On the other hand, since (2 has a small width, the kernel will have a "sharp" component. This may enable fast convergence near the true distribution.
To illustrate the potential use of such a multi-scale kerel,, Fig. compares the performance of kernels with three fixed widths of a E {0.1, 1, 10} with a single kernel concatenated with all three widths. The true and generated data are single point masses with an initial distance of 10. As expected, the very low width kernel (a = 0.1) fails to converge while the wide width kernels (a = 1. 10) converge slowly. In contrast, the concatenated kernel is able to get fast convergence in both the initial and later stages. Of course, further work will be needed to find out the best architectures for networks with multiple widths for complex practical data. In the context of neural network discriminators, such multi-scale kernel behavior may be achieved using parallel networks with varying depths, or the use of skip connections. However, designing such a discriminator requires further investigation.
9 Conclusion
In this paper we propose new framework for understanding behaviors exhibited by training GANs. By assuming isolated neighborhoods around each true point, we can decouple the kernel GAN training dynamics that occur when jointly updating a generator and discriminator. Using this model we theoretically derive conditions that explain well-known training behavior in GANs. While stable local equilibrium exists when true and generated distributions match exactly, bad local minima exist as well. Specifically true point can "greedily" hold onto multiple generated points in region determined by the discriminator kernel width, leading to the phenomenon of approximate mode collapse. We provide theoretical and empirical evidence of a diverging failure mode as well, where one or more generated points completely escape the influence of the true distribution and travel along arbitrary trajectories. Through this analysis, it becomes clear that kernel width in particular plays an important role in this behavior.
There are several possible lines of future work. Most importantly, we have studied a simple GAN without gradient penalties, as commonly used in methods such as [2,3, 13, 17]. Future work can also consider the convergence. Our linearized analysis provides the eigenvalues which can be used for rates close to the equilibrium as performed in (21,22,30) 30]. Finally, there a large body of literature connecting kernels to the neural networks via the so-called neural tangent kernel (NTK) [15] and may be useful to study here as well.
Acknowledgments and Disclosure of Funding
Rangan was supported in part by NSF grants 1952180, 1925079, 1564142, 1547332, the SRC, and the industrial affiliates of NYU WIRELESS.
10

---

References
[1] Hamed Alqahtani. Manolya Kavakli-Thorns and Gulshan Kumar. Applications of Generative Adversarial Networks (GANs): An Updated Review. Archives of Computational Methods in Engineering, 28(2): March 2021.
[2] Martin Arjovsky and Léon Bottou. Towards principled methods for training generative adver- sarial networks, 2017.
[3] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pages 214-223. PMLR, 2017.
[4] Yogesh Balaji, Mohammadmahdi Sajedi, Neha Mukund Kalibhat, Mucong Ding, Dominik Stöger, Mahdi Soltanolkotabi, and Soheil Feizi. Understanding overparameterization in genera- tive adversarial networks, 2021.
[5] Alberto Bietti and Julien Mairal. On the Inductive Bias of Neural Tangent Kernels. In H. Wallach,
H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[6] Mikolaj Binikowski, Danica J Sutherland, Michael Arbel, and Arthur Gretton. Demystifying MMD GANs. arXiv preprint arXiv:1801.01 2018.
[7] Nicolas Bonneel, Michiel Van De Panne, Sylvain Paris, and Wolfgang Heidrich. Displacement interpolation using lagrangian mass transport. In Proceedings of the 2011 SIGGRAPH Asia conference, pages 1-12, 2011.
[8] Ali Borji. Pros and cons of GAN evaluation measures: New developments. CORR, abs/2103. 0.399,9,,9 2021.
[9] lean-vves Franceschi, Emmanuel de Bézenac, Ibrahim Ayed, Mickaël Chen, Sylvain Lamprier, and Patrick Gallinari. neural tangent kernel perspective of gans, 2021.
[10] Ian Goodfellow. Nips 2016 tutorial: Generative adversarial networks. arXiv preprint arXiv:1701.00160 2016.
[11] Ian J. Goodfellow, Jean Pouget-Abadie Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks, 2014.
[12] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773 2012.
[13] Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Improved training of wasserstein gans. arXiv preprint arXiv: 00028, 2017.
[14] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by two time-scale update rule converge to a local nash equilibrium. Advances in neural information processing systems, 30, 2017.
[15] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580, 2018.
[16] Valentin Khrulkov, Artem Babenko, and Ivan Oseledets. Functional space analysis of local gan convergence. International Conference on Machine Learning, pages 5432-5442. PMLR, 2021.
[17] Naveen Kodali, Jacob D. Abernethy, James Hays, and Zsolt Kira. How train your DRAGAN. CoRR, 00s/1705.07215 2017.
[18] Chun-Liang Li, Wei-Cheng Chang, Yu Cheng, Yiming Yang, and Barnabás Póczos. MMD GAN: Towards deeper understanding of moment matching network. Advances in neural information processing systems, 30, 2017.
[19] Lars Mescheder, Andreas Geiger, and Sebastian Nowozin, Which training methods for gans do actually converge?, 2018.
[20] Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of gans. Advances in neural information processing systems, 30, 2017.

---

[21] Youssef Mrouch and Truyen Nguyen. On the convergence of gradient descent in gans: Mmd gan as gradient flow. In International Conference on Artificial Intelligence and Statisties, pages 1720-1728. PMLR, 2021.
[22] Vaishnavh Nagarajan and J. Zico Kolter. Gradient descent gan optimization is locally stable, 2018.
[23] Weili Nie and Ankit B Patel. Towards better understanding and regularization of gan training dynamics. In Uncertainty Artificial Intelligence, pages 281-291. PMLR, 2020.
[24] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt,
D. Koller, Y. Singer, and S. Roweis, editors. Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
[25] Eitan Richardson and Yair Weiss. On gans and gmms. CoRR, abs/1805.12445 2018.
[26] Hoang Thanh- Tung, Truyen Tran, and Svetha Venkatesh. On catastrophic forgetting and mode collapse in generative adversarial networks. CoRR, abs/1807 000///0070441,,, 2018.
[27] Thomas Unterthiner, Bernhard Nessler, Calvin Seward, Günter Klambauer, Martin Heusel, Hubert Ramsauer, and Sepp Hochreiter. Coulomb GANs: Provably optimal Nash equilibria via potential fields. arXiv preprini arXiv: 1708. 088/9, 2017.
[28]
Mathukumalli Vidyasagar. Nonlinear systems analysis, volume 42. Siam, 2002.
[29] Zhengwei Wang, Qi She, and Tomás Ward. Generative adversarial networks in computer vision:
A survey and taxonomy. ACM Computing Surveys, 54:1-38, 02 2021.
[30] Kun Xu, Chongxuan Li, Jun Zhu, and Bo Zhang. Understanding and stabilizing gans" training dynamics with control theory. arXiv preprint arXiv: 13188, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The Introduction has section on main contributions highlight the key items.
(b) Did you describe the limitations of your work? [Yes] The introduction and model clearly define the specific model we are considering. The conclusions describes avenues of future work not considered here.
(c) Did you discuss any potential negative societal impacts of your work? [No] As theoretical result, we did not see any negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] The guidelines are reviewed.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All assumptions stated in the Model section and theorem statements
(b) Did you include complete proofs of all theoretical results? [Yes] They are included in the supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL.? (Yes] Code is added as supplementary material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Main hyperparameters are discussed in the main results, details included in the supplementary
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [No] We considered a large number of trials and took the median.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [No] Due to the simplicity of the experiments, this was not necessary
12

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] We only used standard existing code packages such pytorch.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [No] No new assets were needed
(d) Did you discuss whether and how consent obtained from people whose data you' 're using/curating? [N/A] No subjects were tested.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] No personally identifiable was used.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "gAm8eg4YNWl", "reviewer": "Reviewer_47EW", "summary": "This paper studies the gradient descent-ascent optimization problem of GANs in the following setting:\n 1. without generator, the GAN manipulating a finite set of elements;\n 2. under an MMD GAN model with a fixed kernel, the kernel discriminator optimizing the corresponding IPM;\n 3. in a novel framework called the Isolated Points Model where the kernel value between true data points approaches zero.\n\nThe latter assumptions enable the derivation of new convergence results. The paper particularly characterizes the existence, position and nature of equilibrium points in the gradient descent-ascent optimization around the true samples tanks to the introduction of a probability mass difference criterion. This notably allows the authors to rule out the possibility of strict mode collapse on the one hand and to identify the existence of bad local minima leading to an approximate mode collapse phenomenon. The theoretical results are then assessed experimentally on a toy dataset.", "questions": " - Could the authors further evaluate and discuss the realism of the introduced Isolated Point Model? In particular, how might it relate to the theory of NTKs as mentioned in the conclusion?\n - Would it be possible to highlight how the obtained results and/or the used proof techniques might serve as a basis for future work?\n - Do the authors see any relaxation of the Isolated Point Model and Assumption 1 beyond considering exponentially vanishing kernels like the RBF? For example, by constraining only the gradients of the kernel instead of its values, since the movement of the generated points only depend on its gradients?", "limitations": "The authors adequately present the assumptions and limitations of their study. While many of them are standard and reasonable, further discussion of the realism of the main and novel assumptions would be beneficial for the paper as it could help the reader gauge the impact of the obtained results (cf. the above sections).", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\nThe study of the optimization procedure of GANs is a highly challenging task, as understanding the outcome of its non-convex non-concave behavior remains an open question in the literature. In this regard, **the tackled problem is relevant** to the NeurIPS community.\n\nThis **well-written paper** presents a clear proposition to advance our understanding of this difficult problem. It properly defines its analysis framework composed of assumptions (1, 2, 3) as described in the above summary. While **conditions (1, 2) are reasonable, well-motivated choices** to make the optimization problem amenable to theoretical analysis, the Isolated Point Model (3) necessarily limits the applicability of the presented results. Nonetheless, such a strong assumption is understandable given the challenge of the tackled issues and **pushes back the limits of previous convergence analyses** whose assumptions were even more restrictive.\n\nTo my knowledge, the obtained theoretical results are **clearly presented**, **novel** and **may contribute to a better understanding of GAN optimization**. The identification of precise criteria for the existence of stable and unstable equilibrium points as well as the discovery of an approximate mode collapse is very welcome and participate in deepening our knowledge of local convergence effects in GANs.\n\n### Weaknesses\n\nMy main interrogation on the paper deals with **the significance of the presented results**. Given the restrictions imposed by the Isolated Point Model, their impact on the domain remains unclear and difficult to gauge. Indeed, the proposed Isolated Point Model is **unrealistic** in the context of GANs. While kernel discriminators may be considered via the theory of NTKs [8], these kernels are non-standard and typically do not resemble the RBF-like kernels considered in this paper. Even in the case of the RBF, **a small kernel width is not a typical choice**, as explained by the empirical results of Section 7. This lack of grounding in GAN practice is highlighted by the divergence result of Section 5, which to my knowledge do not correspond to a standard GAN behavior. I am also unable to judge whether the introduced framework might also serve as a basis for future, less limited analyses, as this is a difficult task.\n\n### Overall Sentiment\n\nGiven the difficulty of the tackled problem, the state of the literature on this matter, and the interesting phenomena unveiled by the authors, I think that this paper is worth publishing at NeurIPS.\n\nEven though the chosen setting might be seen as unrealistic, I believe that the presented advances have the potential to be useful to the community, hence my positive recommendation. I would be glad to discuss this matter with the authors and the other reviewers during the discussion phase.\n\n### Typos\n\n - Figure 1: I think the description of $V_4$ in the caption actually corresponds to $V_2$ in the figure.\n - Line 172: \"excactly\" should be \"exactly\".\n - Line 268: \"singl\" should be \"single\".\n - Lines 189, 214, 265 and 295: please fix the quote typesetting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Lek-bw6N7b", "reviewer": "Reviewer_3uQN", "summary": "This article propose a simple theoretical model, called the Isolated Points Model, which is analytically tractable and rigorously study the stability and convergence properties of training a GAN. The article analyze the GAN's training problems from local stability and instability, approximate mode collapse and divergence three perspectives.  Finally, this article argues a kernel based discriminator to explain the above three problems.", "questions": "1. Experiments are too simple to convince the theoritic prove.\n\n2. This article does not supply a useful solution to solve the problems mentioned in the article.\n\n3. Role of the Kernel Width in the section 6 might be a very important factor for the article, but the analysis for this factor are too simple.\n\n4.  In the caption of Figure 1, article states that \"In V4, the excess point mass the $\\triangle_4$ < 0\". But in the V4 of figure 1, the $\\triangle_4=0.25$. Both seetings are contradictory.\n\n5. If the RBF is set as discriminator kernel, how the RBF kernel satisfies the assumption in the equation 10. \n\n6. Substituting equation 6 into equation 5 does not yield equation 4. Because in equation 4 is a(x_i), but the kernel is (a^T)a(x_i).\n\n7. The article migth explain the meaning of $\\delta$ in equation 1.\n", "limitations": "yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This article proposed originality insight for the training of GAN using Isolated Points Model. \n\nWeaknesses:\n1. This article proposed originality insight for the training of GAN, but without a solution for this problems.\n2. There are some problems with the misuse of symbols in the derivation section", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GXWh0gXfBq", "reviewer": "Reviewer_DE8a", "summary": "This paper analyzes the dynamics of training GANs under the case that the true and generated samples are discrete, finite sets, and the discriminator is kernel-based. Specifically, the paper assumes that the true samples are at least one kernel width away from each other, so called Isolated Points Model. This paper analyzes the necessary and sufficient conditions for local stability and instability, points out the existence of approximate mode collapse and divergence, and provides insights into the role of the kernel width of the kernel discriminator. Numerical experiments are also conducted to show the effect of kernel width on GAN training.", "questions": "- What new principles does this study bring to GAN design? In other words, how do we avoid instability and mode collapse in training GANs?\n\ntypos:\n- In line 104, \"generated samples\" -> \"true samples\"", "limitations": "The authors should discuss the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- This paper is well organized and well written.\n- This paper is theoretically grounded. It provides a theoretical understanding of the dynamics of GAN training.\n\n\nWeaknesses\n- Assumptions are strong. For example, in line 110, supposing that N_i^k is constant over time is unreasonable. It is not clear to me at this time how this assumption affects the theoretical results. I would like to see the authors analyze the results when this assumption does not hold.\n- Experiments are weak. Only numerical experiments with simple experimental settings are provided in this work. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept