Title: UNDERSTANDING THE EFFECTIVENESS OF LIPSCHITZ-CONTINUITY IN GENERATIVE ADVERSARIAL NETS

Abstract: In this paper, we investigate the underlying factor that leads to the failure and success in training of GANs. Specifically, we study the property of the optimal discriminative function f * (x) and show that f * (x) in most GANs can only reflect the local densities at x, which means the value of f * (x) for points in the fake distribution (P g ) does not contain any information useful about the location of other points in the real distribution (P r ). Given that the supports of the real and fake distributions are usually disjoint, we argue that such a f * (x) and its gradient tell nothing about "how to pull P g to P r ", which turns out to be the fundamental cause of failure in training of GANs. We further demonstrate that a well-defined distance metric (including the dual form of Wasserstein distance with a compacted constraint) does not necessarily ensure the convergence of GANs. Finally, we propose Lipschitz-continuity condition as a general solution and show that in a large family of GAN objectives, Lipschitz condition is capable of connecting P g and P r through f * (x) such that the gradient ∇ x f * (x) at each sample x ∼ P g points towards some real sample y ∼ P r .

1. INTRODUCTION:

Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) , as a new way of learning generative models, have recently shown promising results in various challenging tasks. Although GANs are popular and widely-used (Isola et al., 2016; Brock et al., 2016; Nguyen et al., 2016; Zhu et al., 2017; Karras et al., 2017) , they are notoriously hard to train (Goodfellow, 2016) . The underlying obstacles, though have been widely studied (Arjovsky & Bottou, 2017; Lucic et al., 2017; Heusel et al., 2017a; Mescheder et al., 2017; 2018; Yadav et al., 2017) , are still not fully understood. In this paper, we study the convergence of GANs from the perspective of the optimal discriminative function f * (x).

We show that in original GAN and its most variants, f * (x) is a function of densities at the current point x but does not reflect any information about the densities/locations of other points in the real and fake distributions. Moreover, Arjovsky & Bottou (2017) state that the supports of real and fake distributions are usually disjoint. In this paper, we argue that the fundamental cause of failure in training of GANs (Section 2.1) stems from the combination of the above two facts. The generator uses ∇ x f * (x) as the guidance for updating the generated samples, but ∇ x f * (x) actually tells nothing about where P r is. Therefore, the generator is not guaranteed to converge to the case P g = P r .

Accordingly, Arjovsky et al. (2017) proposed the Wasserstein distance (in its dual form) as an alternative objective, which can properly measure the distance between two distributions no matter whether their supports are disjoint. However, as shown in Section 2.3, when the supports of the P g and P r are disjoint, the gradient of f * (x) from the dual form of Wasserstein distance given a compacted dual constraint also does not reflect any useful information about other points in P r . Based on this observation, we provide further investigation in Section 2.4 and argue that measuring the distance properly does not necessarily imply that the gradient is well-defined in terms of ∇ x f * (x).

In Section 3, we propose incorporating Lipschitz-continuity condition in the objectives of GANs as a general solution, and prove that in a broad family of discriminator objectives, Lipschitz-continuity condition can build strong connections between P g and P r through f * (x) such that when the supports of P g and P r are disjoint, ∇ x f * (x) at each sample x ∼ P g will point towards some real sample y ∼ P r . This guarantees that P g is moving towards P r at every step.

We extend our discussion on f * (x) and ∇ x f * (x) to the case where the supports of P g and P r are overlapped, and present the general arguments in Section 4.1. Subsequently, in Section 4.2, we show that the locality of f * (x) and ∇ x f * (x) in traditional GANs turns out to be an intrinsic cause to mode collapse. Finally, in Section 4.3, we explain the reason of empirical success of traditional GANs under the circumstance that they have no convergence guarantee.

Table 1 : Comparison of different objectives in GAN models.

φ ϕ F f * (x) JS-Divergence

-log(σ(-x)) -log(σ(x)) {f : R n → R} log Pr(x) Pg(x)

Least Square (x -α) 2 (x -β) 2 {f : R n → R} α•Pg(x)+β•Pr(x) Pg(x)+Pr(x)

Wasserstein-1 with Lip 1 x -x {f : R n → R,

f lip ≤ 1} N/A µ-Fisher IPM x -x {f : R n → R, E x∼µ f (x) 2 ≤ 1} 1 Fµ(Pr,Pg) Pr(x)-Pg(x) µ(x)

2. THE FUNDAMENTAL CAUSE OF FAILURE IN TRAINING OF GANS:

Typically, the objectives of GANs can be formulated as follows:

EQUATION

where P z is the source distribution of the generator (usually a Gaussian distribution) in R m and P r is the target (real) distribution in R n . The generative function g : R m → R n learns to output samples that shares the same dimension as P r , while the discriminative function f : R n → R learns to output a score indicating the authenticity of a given sample. We denote the implicit distribution of the generated samples as P g , i.e., P g = g(P z ).

F and G denote discriminative and generative function spaces parameterized by neural networks, respectively; functions φ, ϕ, ψ: R → R are loss metrics. We list the choices of F, φ and ϕ in some representative GAN models in Table 1 , where we denote f * = arg min f ∈F J D .

In these GANs, the gradient that the generator receives from the discriminator with respect to a generated sample x ∼ P g is

∇ x J G (x) = ∇ f (x) ψ(f (x)) • ∇ x f (x).

(2) In Eq. ( 2), the first term ∇ f (x) ψ(f (x)) is a step-related scalar that is out of the scope of our discussion in this paper; the second term ∇ x f (x) is a vector indicating the direction that the generator should follow for optimizing on sample x.

2.1 ∇ x f * (x) ON P g DOES NOT REFLECT USEFUL INFORMATION ABOUT P r

In this section, we will show that when the supports of P g and P r are disjoint, ∇ x f * (x) in traditional GANs does not reflect any useful information about P r , and P g is not guaranteed to converge to P r . We argue that this is the fundamental cause of non-convergence and instability in traditional GANs.1 

2.1.1. THE ORIGINAL GAN AND LEAST-SQUARES GAN:

In the simplest case of Eq. ( 1), e.g., the original GAN (Goodfellow et al., 2014) and Least-Squares GAN (Mao et al., 2016) , there is no restriction on F. Therefore, f * (x) for each point x is independent of other points, and we have f * (x) = arg min f (x)∈R P g (x) • φ(f (x)) + P r (x) • ϕ(f (x)), ∀x.

(3)

Since we assume supports of P g and P r are disjoint, we further have f * (x) = arg min f (x)∈R P g (x) • φ(f (x)), ∀x ∼ P g , arg min f (x)∈R P r (x) • ϕ(f (x)), ∀x ∼ P r . In traditional GANs, f * (x) is only defined on the supports of P g and P r and its values do not reflect any information about the locations of other points in P g and P r . Therefore, they have no guarantee on the convergence. Wasserstein distance in a compacted dual form suffers from the same problem. GANs under Lipschitz constraint builds connection between P g and P r , where ∇ x f * (x) pulls P g towards P r .

For x ∼ P g , the value of f * (x) is irrelevant to P r . Since P g and P r are disjoint2 , ∇ x f * (x) for x ∼ P g also tells nothing about P r . In consequence, the generator can hardly learn useful information and is not guaranteed to converge to the case where P g = P r .

2.1.2 THE FISHER GAN Mroueh et al. (2017) prove that the optimal f * of µ-Fisher IPM F µ (P r , P g ), the objective used in Fisher GAN (Mroueh & Sercu, 2017) , has the following form

EQUATION

)

where µ is a distribution whose support covers P r and P g . Given P r and P g are disjoint, we have

EQUATION

Note that the scalar 1 Fµ(Pr,Pg) is a constant. Eq. ( 6) also defines f * (x) on P g and P r independently. Therefore, for x ∼ P g , f * (x) and ∇ x f * (x) tell nothing about P r .

2.2. CONNECTION TO GRADIENT VANISHING:

The non-convergence problem of the original GAN has once been considered as the gradient vanishing problem. In (Goodfellow et al., 2014) , it is addressed by using an alternative objective for the generator. However, it actually only changes the scalar ∇ f (x) ψ(f (x)) while the aforementioned problem in ∇ x f * (x) still exists. The least-squares GAN (Mao et al., 2016) is proposed to address the gradient vanishing problem, but it also focuses on ∇ f (x) ψ(f (x)) basically. As we have discussed, the least-squares GAN also belongs to traditional GANs, which is not guaranteed to converge when P g and P r are disjoint. Arjovsky et al. (2017) provided a new perspective on understanding the gradient vanishing problem. They argued that gradient vanishing stems from the ill-behaving of traditional metrics, i.e., the distance between P g and P r remains constant when they are disjoint. Wasserstein distance is thus proposed as an alternative metric, which can properly measure the distance between two distributions no matter they are disjoint or not. However, as we will show next, Wasserstein distance may also suffer from the same problem on ∇ x f * (x), if a more compact dual form is used.

In summary, gradient vanishing is about the scalar term ∇ f (x) ψ(f (x)) in ∇ x J G (x) or the overall scale of ∇ x J G (x), and in this paper we investigate its direction ∇ x f * (x), where the problem is so fundamental and challenging that even the Wasserstein distance, which can properly measure the distance for disjoint distributions, may also suffer from the same issue.

2.3. WASSERSTEIN DISTANCE IN COMPACT DUAL FORM SUFFERS FROM THE SAME PROBLEM:

The (1 st -)Wasserstein distance is a distance function defined between two probability distributions:

W 1 (P r , P g ) = inf π∈Π(Pr,Pg)

EQUATION

where Π(P r , P g ) denotes the collection of all probability measures with marginals P r and P g on the first and second factors, respectively. Since solving it in the primal form (Eq. ( 7)) is burdensome, Wasserstein distance is usually solved in its dual form. Though Wasserstein distance in its dual form is usually written with Lipschitz constraint, we here provide a more compact version. The proof of this dual form can be found in Appendix I.

EQUATION

We leave the detailed discussion on the relationship between Lipschitz-continuity and Wasserstein distance in Section 4.4. In Eq. ( 8), we replace the strong Lipschitz constraint with a looser constraint. Note that Eq. ( 7) and Eq. ( 8) are still equivalent. With this dual form, we will demonstrate that a well-defined distance metric, i.e., Wasserstein distance in this compacted dual form, may also suffer from the same problem in ∇ x f * (x) and does not necessarily ensure the convergence of GANs.

We now study the optimal discriminative function f * (x) of Wasserstein distance in this dual form.

Since there is generally no closed-form solution for f * (x) in Eq. ( 8), we use an illustrative example for demonstration here, but the conclusion is general. Let Z ∼ U [0, 1] be a uniform variable on interval [0, 1], P g be the distribution of (1, Z) ∈ R 2 , and P r be the distribution of (0, Z) ∈ R 2 , as shown in Figure 1 . According to Eq. ( 8), one of the optimal f * is as follows

EQUATION

Though having the constraint "f (x) -f (y) ≤ d(x, y), ∀x ∼ P r , ∀y ∼ P g ", Wasserstein distance in this dual form also only defines the value of f * (x) on the supports of P g and P r , and the values of f * (x) on P g contain no useful information about the location of P r . Therefore, if P g and P r are disjoint, ∇ x f * (x) hardly provides useful information to the generator about "how to change P g into P r " and the generator is not guaranteed to converge to the case P g = P r . It is worth noticing that the value of f * (x) on the region other than the supports of P g and P d is still undefined.

2.4. A WELL-DEFINED METRIC DOES NOT NECESSARILY GUARANTEE THE CONVERGENCE:

The objectives of GANs are usually defined as (or proved equivalent to) minimizing a distance metric between P g and P r , which implies that "P g = P r is the unique global optimum", and is in accordance with the final goal of the generative model, i.e., estimating the distribution of real samples. However, in this section, we emphasize that a smooth distance metric satisfying "P g = P r is the optimum" does not necessarily guarantee the convergence of GANs.

Given an objective is convex with respect to P g and holds the property that "P g = P r is the unique optimum", the convergence of GANs is guaranteed if only they are directly optimizing P g , i.e., "dragging" P g to P r . However, what they actually do is using ∇ x f * (x) as the guidance to optimize the generated samples. As shown in previous sections, when P g and P r are disjoint, ∇ x f * (x), i.e., the direction that the generator follows for updating the generated samples, tells nothing about how to pull P g to P r . In this way, the convergence of GANs are not necessarily guaranteed. ∇ x f * (x) indeed indicates the direction of decreasing the objective in terms of the current f * (x), but updating x to make the value of f * (x) increase / decrease does not necessarily imply that P g is getting closer to P r . Recall that in the failure case of Wasserstein distance dual form in the above section, the values of f * (x) on P g is zero, while the values of f * (x) around P g is undefined.

In conclusion, a smooth distance metric satisfying "P g = P r is the optimum" does not guarantee the convergence and sample updating according to ∇ x f * (x) does not necessarily decrease the distance between P g and P r . Therefore, if we use ∇ x f * (x) for updating the generator, it is necessary to make ∇ x f * (x) aware of how to pull P g to P r . Alternative strategies actually exist, for example, Sanjabi et al. (2018) use the optimal transport plan (Seguy et al., 2017) between P g and P r to update the generator. However, their results tend to be blurry. In the next section, we will introduce the Lipschitz constraint as a general solution for making ∇ x f * (x) well-behaving and guaranteeing the convergence of ∇ x f * (x)-based GANs.

3. A GENERAL SOLUTION: LIPSCHITZ CONDITION:

Lipschitz-continuity constraint becomes popular in GANs recently as part of the discriminator's objective (Arjovsky et al., 2017; Kodali et al., 2017; Fedus et al., 2017; Miyato et al., 2018) , achieving great success. In this section, we explain the significance of Lipschitz constraint when introduced into the objective of the discriminator. In a nutshell, under a board family of GAN objectives, Lipschitz constraint is able to connect P g and P r through f * (x) such that when P r and P g are disjoint, ∇ x f * (x) for each generated sample x ∼ P g will point towards some real sample y ∼ P r , which guarantees the trend that "P g is getting closer to P r at every step".

3.1. THE MAIN RESULT:

A function f : X → Y is k-Lipschitz continuous if it satisfies the following property:

EQUATION

where d X and d Y are distances metrics in domains X and Y , respectively. The smallest constant k is called the Lipschitz constant of function f . In this paper (and most GAN papers), d X and d Y are defined as Euclidean distance. 3 We let y-x denote Euclidean distance.

As proved by Gulrajani et al. (2017) , when the Lipschitz condition is combined with Wasserstein distance, we have the following property if f * (x) is differentiable, then

EQUATION

where x t = tx + (1 -t)y, 0 ≤ t ≤ 1, and π * is the optimal π in Eq. ( 7). The meaning of this proposition is two-fold: (i) for each x ∼ P g , there exists a y ∼ P r such that ∇ x f * (x t ) = y-x y-x for all linear interpolations x t between x and y; (ii) these (x, y) pairs match the optimal coupling π * .

Next we introduce our theorem on the Lipschitz condition. It turns out when combining the Lipschitz condition with generalized objectives, Property-(i) still holds and Property-(ii) is naturally dismissed as it is now not restricted to Wasserstein distance.

Theorem 1. Let J D E x∼Pg [φ(f (x))] + E x∼Pr [ϕ(f (x))

] and ∂ x J D denotes P g (x)φ(f (x)) + P r (x)ϕ(f (x)). Let Pr and Pg denote the supports of P r and P g , respectively. Assume

f * = arg min f [J D + λ • k(f ) 2 ],

where k(f ) is the Lipschitz constant of f . If φ(x) and ϕ(x) in J D satisfy

     φ (x) > 0, φ (x) ≥ 0, ϕ (x) < 0, ϕ (x) ≥ 0, ∃ a, φ (a) + ϕ (a) = 0, (12) then we have that (a) ∀x ∈ Pg ∪ Pr , ∃y =x ∈ Pg ∪ Pr such that |f * (y)-f * (x)| = k(f * ) • x-y or ∇ f * (x) ∂ x J D = 0; (b) ∀x ∈ Pg ∪ Pr -Pg ∩ Pr , ∃y =x ∈ Pg ∪ Pr such that |f * (y)-f * (x)| = k(f * ) • x-y ; (c) if Pg = Pr and P g = P r , then ∃x, ∃y =x such that |f * (y)-f * (x)| = k(f * ) • x-y ; (d) the only Nash Equilibrium of J D + λ • k(f ) 2 is reached when P g = P r , where k(f ) = 0.

The above theorem states that when the Lipschitz condition is combined with an objective that satisfies Eq. ( 12), then: (a) for the optimal discriminative function f * (x) at any point x ∈ Pg ∪ Pr , it either is bounded by the Lipschitz constant or ∂ x J D holds a zero-gradient with respect to f * (x); (b) for any point that only appears in Pg or Pr , there must exist a point that bounds this point in terms of |f * (y)-f * (x)| = k(f * ) • x-y , because for these points, ∂ x J D will never get zero gradient with respect to f * (x) as we prove in the Appendix G; (c) when P g and P r are totally overlapped, as long as P g still not converges to P r , there exists at least one pair (x, y) that bounds each other; (d) the only Nash Equilibrium among P g and f * (x) under this objective is "P g = P r with k(f * ) = 0". The formal proof is in Appendix G.

Wasserstein distance, i.e., φ(x) = ϕ(-x) = x is one instance that satisfies Eq. ( 12); and it is a very special case, which holds φ (x) = 0 and ϕ (x) = 0. Eq. ( 12) is actually quite general and there exists many other settings, e.g., φ

(x) = ϕ(-x) = -log(σ(-x)), φ(x) = ϕ(-x) = x + √ x 2 + 1 and φ(x) = ϕ(-x) = exp(x). Generally, it is feasible to set φ(x) = ϕ(-x).

As such, to build a new objective, one only needs to find a function that is increasing and has non-decreasing derivative. See Figure 12 . In addition, all linear combinations of feasible (φ, ϕ) pairs also lie in the family.

It is worth noting that k(f ) is also optimized here and it is actually necessary for Property-(c) and Property-(d) . This is the key difference when the Lipschitz condition is extended to general objectives. The underlying reason for the need of also minimizing k(f ) comes from the existence of case "∇ f * (x) ∂ x J D = 0 for P g (x) = P r (x)", which does not hold when the objective is Wasserstein distance. Minimizing k(f ) guarantees that the only Nash Equilibrium is "P g = P r with k(f * ) = 0". On the other hand, if k(f ) is not minimized towards zero, Wasserstein distance dual form based GANs are not guaranteed to have zero gradient ∇ x f * (x) at the convergence state P g = P r . It indicates that minimizing k(f ) is also beneficial to the Wasserstein GAN (Arjovsky et al., 2017) .

3.2 LIPSCHITZ CONDITION CONNECTS P g AND P r THROUGH f * (x)

From Theorem 1, we know that for any point x, as long as ∂ x J D does not hold a zero gradient with respect to f * (x), f * (x) must be bounded by another point

y such that |f * (y) -f * (x)| = k(f * ) • x-y .

We here further clarify that, when there is a bounding relationship, it must involve both real sample(s) and fake sample(s). More formally, we have

Theorem 2. If f * = arg min f [J D + λ • k(f ) 2 ], then • ∀x ∈ Pg , if ∃z =x ∈ Pg ∪ Pr such that |f * (x)-f * (z)| = k(f * ) • x-z , then ∃y =x ∈ Pr such that f * (y)-f * (x) = k(f * ) • x-y , • ∀y ∈ Pr , if ∃z =y ∈ Pg ∪ Pr such that |f * (z)-f * (y)| = k(f * ) • z-y , then ∃x =y ∈ Pg such that f * (y)-f * (x) = k(f * ) • x-y .

The intuition behind the above theorem is that samples from the same distribution, e.g., the fake samples, will not bound each other. It is worth noticing that there might exist a chain of bounding relationships that involves a dozen of fake samples and real samples, and these points all lie in the same line and bounds each other.

Under the Lipschitz condition, the bounded line in the value surface of f * is the basic building block that connects P g and P r , and each fake sample lies in one of the bounded lines. Next we will further interpret the implication of bounding relationship and show that it guarantees meaningful ∇ x f * (x) for all involved points.

3.3. LIPSCHITZ CONDITION ENSURES THE CONVERGENCE OF:

∇ x f * (x)-BASED GANS

Recall that the proposition in Eq. ( 11) states that ∇ x f * (x t ) = y-x y-x . This is actually a direct consequence of bounding relationship between x and y. We formally state it as follows:

Theorem 3. Assume f (x) is differentiable and k-Lipschitz continuous. For all x and y which satisfy x = y and f (y

)-f (x) = k• x-y , we have ∇ x f (x t ) = k• y-x y-x , where x t = tx+(1-t)y for 0 ≤ t ≤ 1.

In other words, if two points x and y bound each other in terms of f (y)-f (x) = k • x-y , there is a straight line between x and y in the value surface of f . Any point in this line holds the maximum gradient slope k, and the direction of these gradient all point towards the x → y direction. Combining Theorem 1 and Theorem 2, we can conclude that when P g and P r are disjoint, ∇ x f * (x) for each sample x ∼ P g points to a sample y ∼ P r , which guarantees that P g is moving towards P r .

In fact, Theorem 1 provides further guarantee on the convergence. Property-(b) implies that for any x ∼ P g that does not lies in P r , ∇ x f * (x) points to some real sample y ∼ P r . In the fully overlapped case, according to Property-(c), unless P g = P r , there exists a pair (x, y) in bounding relationship and ∇ x f * (x) pulls x towards y. Property-(d) guarantees that the only Nash Equilibrium is "P g = P r ". The proof of Theorem 3 is provided in Appendix D. densities P g (x) and P r (x) . Given f * (x) is an increasing function of P r (x) and decreasing function of P g (x), when fake samples get close to a mode of the P r , ∇ x f * (x) move them towards the mode.

4. EXTENSIONS AND DISCUSSIONS:



4.1. FROM DISJOINT CASE TO OVERLAPPING CASE:

In Section 2, we discuss the problem of f * (x) and ∇ x f * (x) in the case where P g and P r are disjoint. In this section, we extend our discussion to the overlapping case. In the disjoint case, we argue that "f * (x) on P g does not reflect any information about the location of other points in P r " will lead to an unfeasible ∇ x f * (x) and thus non-convergence. In the overlapping and continuous case, things are actually different, f * (x) around each point is also defined, and its gradient ∇ x f * (x) now reflects the local variation of f * (x).

For most traditional GANs, f * (x) mainly reflects the local information about the density P g (x) and P r (x). However, it is worth noting that f * (x) is usually an increasing function with respect to P r (x) while a decreasing function with respect to P g (x). For instance, f * (x) in the original GAN is log P r (x)/P g (x). Optimizing the generator according ∇ x f * (x) will move sample x towards the direction of increasing f * (x). Because f * (x) positively correlates with P r (x) and negatively correlated with P g (x), it in sense means x is becoming more real. However, such a local greedy strategy turns out to be a fundamental cause of mode collapse.

4.2. THE CAUSE OF MODE COLLAPSE: THE LOCALITY OF f * (x) AND ∇:

Mode collapse is a notorious problem in GANs' training, which refers to the phenomenon that the generator only learns to produce part of P r . Many literatures try to study the source of mode collapse (Che et al., 2016; Metz et al., 2016; Kodali et al., 2017; Arora et al., 2017) and measure the degree of mode collapse (Odena et al., 2016; Arora & Zhang, 2017) .

The most recognized cause of mode collapse is that, if the generator is much stronger than the discriminator, it may learn to only produce the sample(s) in the local or global maximum of f (x) for the current discriminator. This argument is true for most of GAN models. However, from our perspective on f * (x) and its gradient, there actually exists a much more fundamental cause of mode collapse, i.e., the locality of f * (x) in traditional GANs and the locality of gradient operator ∇.

In traditional GANs, f * (x) is a function of local densities P g (x) and P r (x), which is local, and the gradient operator ∇ is also a local operator. As the result, ∇ x f * (x) only reflects its local variations and cannot capture the statistic of P r and P g that is far from itself. If f * (x) in the surrounding area of x is well-defined, ∇ x f * (x) will move x towards the nearby location where the value of f * (x) is higher. It does not take the global status into account.

The typical result is that when fake samples get close to a mode of the P r , they move towards the mode and get stuck there (due to the locality). Assume P r consists of two Gaussian distributions (A and B) that are distant from each other, while the current P g is uniformly distributed over its support and close to real Gaussian A. In this case, ∇ x f (x) of all fake samples will point towards the center of Gaussian A. If P g is a Gaussian with the same standard deviation as Gaussian A, ∇ x f (x) in original GAN and Least-Square GAN shows almost identical behaviors, which is illustrated in Figure 2 . In Fisher GAN, if µ(x) is uniform, the case is even worse: a large amount of points that are relatively far from Gaussian A will move away from A (but the direction is not necessarily towards B, though in our 1-D case it is). This observation again supports our argument that "a well-defined distance metric does not necessarily guarantee the convergence", and the validity of ∇ x f * (x) is still necessary even if P g and P r is continuous and overlapped.

4.3. EXPLANATION ON THE EMPIRICAL SUCCESS OF TRADITIONAL GANS:

Though traditional GANs does not have any guarantee on its convergence, it has already achieved its great success. The reason is that having no guarantee does not mean it cannot converge. It turns out extensive parameter-tuning actually increases the probability of the convergence.

As shown in Appendix A, hyper-parameters are important in influencing the value surface of f * (x). Some typical settings (e.g., simplified neural network architecture, relu or leaky relu activation, relatively high learning rate, Adam optimizer, etc.) tend to form a relatively smooth value surface (e.g., monotonically increasing from P g to P r ), making ∇ x f * (x) much more meaningful. That is, one can find these settings, where ∇ x f * (x) or ∇ x f (x) is more favourable, to enable traditional GANs to work. In opposite, we have tried highly-nonlinear activation such as swish (Ramachandran et al., 2018) in the discriminator. It turns out traditional GANs are very likely to fail. In contrast, our proposed Lipschitz constraint based GANs are compatible with highly-nonlinear activation. Another important empirical technique is to delicately balance the generator and the discriminator or limit the capacity of the discriminator. This is to avoid the fatal optimal f * (x). All these could possibly make traditional GANs work. However, the consequence is that these GANs are very sensitive to hyper-parameters and hard to use.

4.4. THE RELATION BETWEEN LIPSCHITZ CONDITION AND WASSERSTEIN DISTANCE:

Most literature presents the dual form of Wasserstein distance with the Lipschitz condition. However, it is worth noticing that the Lipschitz condition is actually stronger than the necessary one in the dual form of Wasserstein distance. Recall that in the dual form of Wasserstein distance, the constraint can be more compactly written as (introduced in Section 2.3 and proved in Appendix I)

EQUATION

However, it is usually written as 1-Lipschitz condition, which is

EQUATION

The key difference is that the constraint in Eq. ( 13) restricts the range of x and y, but Lipschitz condition (Eq. ( 14)) does not have the restriction on the range, thus the latter is the sufficient condition of the former one. It is also worth noticing that, though Lipschitz condition is stronger than the compact one, it does not affect the final solution (Appendix I). In other words, Lipschitz condition is a safe extension of the compact constraint. And if the supports of P g and P r are the entire space, Eq. ( 13) and Eq. ( 14) are actually identical; in such condition, Wasserstein distance in its dual form always works. However, P g and P r are usually disjoint in GANs. Therefore, using the strong Lipschitz condition is necessary to ensure the validity of the dual form of Wasserstein distance in ∇ x f * (x)-based updating, and the constraint in Eq. ( 13) is not enough as shown in Section 2.3.

4.5. CONTRIBUTION CLARIFICATION:

This work is substantially different from Wasserstein GAN (Arjovsky et al., 2017) . Though the final solution in Wasserstein GAN is sound, its main argument is off the point. The main argument for the benefit of Wasserstein distance in (Arjovsky et al., 2017) is that it can properly measure the distance between two distributions no matter whether their supports are disjoint, i.e., Wasserstein distance is a good distance metric. However, according to our analysis in Section 2.4, a proper distance metric does not necessarily ensure the convergence of GAN; more specifically, Wasserstein distance in the dual form with compacted constraint also cannot provide meaningful gradient through ∇ x f * (x).

In addition, we have shown that Lipschitz constraint is able to ensure the convergence of GANs in a family of GAN objectives, which is not restricted to Wasserstein distance. For example, Lipschitz constraint is also introduced to original GAN in (Miyato et al., 2018; Kodali et al., 2017) and shows improvements on the quality of generated samples. As a matter of fact, the original GAN objective φ(x) = ϕ(-x) = -log(σ(-x)) is another instance in our proposed family and thus our analysis explains why and how it works.

It is also worth noticing that J D in our formulation is not derived from any well-established distance metric; it is derived based on Lipschitz constraint. As we have shown that a well-established distance or divergence does not necessarily ensure the convergence, we hope our trial could shed light on the new direction of GANs.

Last but no least, though we do not discuss the generator's objective, our analysis indicates that the minimax in terms of ψ in Eq. ( 1) is not essential, because it only influences the scale of the gradient. Nevertheless, the function ψ does influence the updating of the generator, and we leave the detailed investigation as future work. Another example that has a theoretically meaningful ∇ x f * (x) is Coulomb GAN (Unterthiner et al., 2017) , which is also derived neither from minimax game nor from well-defined distance metric.

4.6 RELATED WORK Fedus et al. (2017) also argued that divergence is not the primary guide of the training of GANs and pointed out that the gradient does not necessarily related to the divergence. However, they tended to believe that original GAN with non-saturating generator objective can somehow work. As we have proved before, given the optimal f * , the original GAN has no guarantee on its convergence. And we argue that practical work scenarios benefit from parameter-tuning.

Some work study the suboptimal f (x) (Mescheder et al., 2017; 2018; Arora et al., 2017) , which is another important direction for understanding GANs theoretically. While the behaviors of suboptimal can be slightly different, we think the optimal f * (x) should well-behave in the first place.

Researchers also found that applying Lipschitz constraint to the generator also benefits the quality of generated samples (Zhang et al., 2018; Odena et al., 2018) . In addition, researchers also investigated implementation of Lipschitz constraint in GANs (Gulrajani et al., 2017; Petzka et al., 2017; Miyato et al., 2018) . However, this branch of related work is out of scope of the discussion in this paper.

5. EXPERIMENTS:

In this section, we present the experiment results on our proposed objectives for GANs. The anonymous code is provided at http://bit.ly/2Kvbkje. We verify a set of φ and ϕ satisfying Eq. ( 12): (a)

5.1. VERIFYING THE OBJECTIVE FAMILY AND ITS:

GRADIENT ∇ x f * (x) (a) x (b) -log(σ(-x)) (c) x + √ x 2 + 1 (d) exp(x)

φ(x) = ϕ(-x) = x; (b) φ(x) = ϕ(-x) = -log(σ(-x)); (c) φ(x) = ϕ(-x) = x + √ x 2 + 1; (d) φ(x) = ϕ(-x) = exp(x).

As shown in Figure 3 , the gradient of each generated sample is towards a real sample.

We further verify ∇ x f * (x) with the real-world data, using ten CIFAR-10 images as P r and ten noise images as P g to make the solving of f * (x) feasible. The result is shown in Figure 4 , where The leftmost in each row are the x ∼ P g and the second are their gradient ∇ x f (x). The interior are x + • ∇ x f (x) with increasing , which will pass through a real sample, and the rightmost are the nearest y ∼ P r . This result visually demonstrates that the gradient of a generated sample is towards the direction of one real sample. Note that the final results of this experiment keep almost identical when varying the loss metric φ(x) and ϕ(x) in the family. Wasserstein distance is a special case in our proposed family of objectives where φ (x) = ϕ (x) = 0. As a result, f * (x) under the Wasserstein distance objective where φ(x) = ϕ(-x) = x has a free offset, which means given a f * (x), f * (x) + b with any b ∈ R is also an optimal. In practice, this behaves as an oscillatory f (x) during training. Any other instance of our new proposed objectives does not have this problem. We illustrate this practical difference in Figure 5 . Finally, we fix ψ(x) = -x in the generator's objective and compare various objectives on unsupervised image generation tasks. The results of Inception Score (Salimans et al., 2016) and Frechet Inception Distance (Heusel et al., 2017b) are presented in Table 2 . We also include the hinge loss φ(x) = ϕ(-x) = -min(0, -x -1) which used in (Miyato et al., 2018) . We use a classifier on Oxford 102 Flower Dataset for the evaluation of FID and Inception Score for results on Oxford 102.

5.3. BENCHMARK ON UNSUPERVISED IMAGE GENERATION TASKS:

The gradient of exp(x) varies significantly and we find it requires a small learning rate to avoid explosion. The objectives x + √ x 2 + 1 and -log(σ(-x)) achieve the best performances. This is probably because they have bounded gradient and reduce the gradient of well-identified points towards zero, which enables the discriminator to pay more attention to these ill-identified. Hinge loss -min(0, -x -1) does not lie in our proposed objective family and turns out to be unstable and performs unsatisfactory in same cases. We also plot the training curve in terms of FID in Figure 6 .

Due to page limitation, we leave the details, visual results and more experiments in the Appendix.

6. CONCLUSION:

In this paper we have shown that the fundamental cause of failure in training of GANs stems from the unreliable ∇ x f * (x). Specifically, when P g and P r are disjoint, ∇ x f * (x) for fake sample x ∼ P g tells nothing about P r , making it impossible for P g to converge to P r . We have further demonstrated that even Wasserstein distance in a more compact dual form (still is equivalent to Wasserstein distance and can properly measure the distance between distributions) also suffers from the same problem when P g and P r are disjoint. This implies that "whether a distance metric can properly measure the distance" does not yet touch the key of non-convergence of GANs. We have highlighted in this paper that a well-defined distance metric does not necessarily guarantee the convergence of GANs because its ∇ x f * (x) can be meaningless. Therefore, if we update the generator based on ∇ x f * (x), we need to pay more attention on the design of f * (x). Furthermore, to address the aforementioned problem, we have proposed the Lipschitz-continuity condition as a general solution to make ∇ x f * (x) reliable and ensure the convergence of GANs, which works well with a large family of GAN objectives. In addition, we have shown that in the overlapping case, ∇ x f * (x) is also problematic which turns out to be an intrinsic cause of mode collapse in traditional GANs.

A EXPERIMENTS: THE INFLUENCE OF HYPER-PARAMETERS:

The value surface of traditional GANs is highly depended on the network and training hyperparameters. We here plot the value surface of Least-Square GAN with various hyper-parameter settings, to give directly impression on how these parameters influence GANs training. Not very strictly, but our empirical code is: (i) a low-capacity network tends to learn a simple surface; (ii) SGD tends to learn a more complex surface than ADAM; (iii) large learning rate tends to learns a simpler surface than small learning rate; (iv) highly nonlinear activation function tends to result in more complex value surface.

Though hyper-parameters tuning could possibly make traditional GANs work, it also makes these GANs hard to use, sensitive to hyper-parameters and easily broken. B VARIOUS φ(x) AND ϕ(x) THAT SATISFIES EQ. 12 For Lipschitz constraint based GANs, φ(x) and ϕ(x) are required to satisfy Eq. 12. Eq. ( 12) is actually quite general and there exists many other instances, e.g.,

φ(x) = ϕ(-x) = x, φ(x) = ϕ(-x) = -log(σ(-x)), φ(x) = ϕ(-x) = x + √ x 2 + 1, φ(x) = ϕ(-x) = exp(x), etc.

We plot these instances of φ(x) and ϕ(x) in Figure 12 .

Generally, it is feasible to set φ(x) = ϕ(-x). Note that rescaling and offsetting along the axes are trivial operation to found more φ(x) and ϕ(x) within a function class, and linear combination of two or more φ(x) or ϕ(x) from different function classes also keep satisfying Eq. 12. 

D PROOF OF THEOREM 3 AND THE NECESSITY OF EUCLIDEAN DISTANCE:

In this section, we delve deeply into the relationship between gradient properties and different norms in Lipschitz-continuity condition. We will prove Theorem 3, i.e. Lipschitz continuity with l 2norm (Euclidean Distance) can guarantee the gradient direction of ∇f * (x), and at the same time, demonstrate that the other norms do not have this property. To start with, we give the proof of Theorem 3 in the following.

Proof.

Let (x, y) be such that x = y, and we define

x t = x + t • (y -x) with t ∈ [0, 1]. We claim that: if f (x) is k-Lipschitz with respect to . p and f (y) -f (x) = k x -y p , then f (x t ) = f (x) + t • k x -y p .

As we know f (x) is k-Lipschitz, with the property of norms, we have

EQUATION

)

Given f (x) -f (y) = k x -y p , it implies all the inequalities need to be equalities. Therefore,

EQUATION

)

Note that v 2 = y-x y-x 2 2 = 1, i.e. v is a unit vector. Now,

EQUATION

)

As the equality holds only when ∇f (x t ) = kv = k y-x y-x 2 , we prove that ∇f (x t ) = k y-x y-x 2 .

Above proof utilizes the property that ∇f (x t ) 2 ≤ k, which is derived from that f (x) is k-Lipschitz with respect to . 2 . However, other norms do not hold this property. Specifically, according to the theory in (Shalev-Shwartz et al., 2012) : if a convex and differentiable function f is k-Lipschitz over S with respect to norm . p , then the Lipschitz continuity actually implies a bound on the dual norm of gradients, i.e. ∇f q ≤ k. Here . q is the dual norm of . p , which satisfies the equation that 1 p + 1 q = 1. As we could notice, a norm is equal to its dual norm if and only if p = 2. Switching to l p -norm with p = 2, it is actually bounding the l q -norm of the gradients. However, bounding the l q -norm of the gradients does not guarantee the gradient direction at fake samples point towards real samples. A counter-example is provided as follows.

Consider a function g(x, y)

= x + y on R 2 . ∀ p 1 = (x 1 , y 1 ), p 2 = (x 2 , y 2 ), there is g(p 1 ) -g(p 2 ) = g(x 1 , y 1 ) -g(x 2 , y 2 ) = (x 1 -x 2 ) + (y 1 -y 2 ) ≤ |x 1 -x 2 | + |y 1 -y 2 | = p 1 -p 2 1

, which means g is a 1-Lipschitz function with respect to l 1 -norm. According to above analysis, the dual norm of ∇g is bounded, i.e. ∇g ∞ ≤ 1. Actually ∇g is equal to (1, 1) at every point in R 2 with ∇g ∞ = 1. Selecting two points A = (0, 0) and B = (2, 1), we have g(A)-g(B) = A-B 1 , however, ∇g(A) = (1, 1) is not pointing towards B.

E ON THE IMPLEMENTATION OF K-LIPSCHITZ FOR GANS:

Typical techniques for enforcing k-Lipschitz includes: spectral normalization (Miyato et al., 2018) , gradient penalty (Gulrajani et al., 2017) , and Lipschitz penalty (Petzka et al., 2017) . Before moving into the detailed discussion of these methods, we would provide several important notes in the first place.

Firstly, enforcing k-Lipschitz in the blending-region of P g and P r is actually sufficient. Define

B(µ, ν) = {x = x • t + y • (1 -t) | x ∼ µ∧y ∼ ν ∧t ∈ [0, 1]}. It is clear that f (x) is 1-Lipschitz in B(µ, ν) implies f (x) -f (y) ≤ d(x,

y), ∀x ∈ µ, ∀y ∈ ν. Thus, it is a sufficient constraint for Wasserstein distance in Eq. 8. In fact, f (x) is k-Lipschitz in B(P g , P r ) is also a sufficient condition for all properties described in Lipschitz constraint based GANs (Section 3).

Secondly, enforcing k-Lipschitz with regularization would provide a dynamic Lipschitz constant k.

Theorem 4. With Wasserstein GAN objective, we have

min f ∈Fk-Lip J D (f ) = k•min f ∈F1-Lip J D (f ).

Assuming we know and can control the Lipschitz constant k of f (x), by introducing a loss, saying square loss, on k respecting to a constant k 0 , the total loss of the discriminator (critic) becomes

J(k) min f ∈Fk-Lip J D (f ) + λ • (k -k 0 ) 2 . With Lemma 4, let α = -min f ∈F1-Lip J D (f ), then J(k) = -k • α + λ • (k -k 0 ) 2 ,

and J(k) achieves its minimum when k = α 2λ + k 0 . When α goes to zero, i.e. P g converges to P r , the optimal k decreases. And when P g = P r , we have α = 0 and optimal k = k 0 . We choose k 0 = 0 in our experiments. The similar analysis applies to Lipschitz constraint based GANs and we use λ • k 2 to enforcing k-Lipschitz for general Lipschitz constraint based GANs.

For practical methods, though spectral normalization (Miyato et al., 2018) recently demonstrates their excellent results in training GANs, spectral normalization is an absolute constraint for Lipschitz over the entire space, i.e., constricting the maximum gradient of the entire space, which is unnecessary. On the other side, we also notice both penalty methods proposed in (Gulrajani et al., 2017) and (Petzka et al., 2017) are not the exactly implementing the Lipschitz continuity condition, because it does not simply penalty the maximum gradient, but penalties all gradients towards 1, or penalties all these greater than one towards 1.

We found in our experiments that the existing methods including spectral normalization (Miyato et al., 2018) , gradient penalty (Gulrajani et al., 2017) , and Lipschitz penalty (Petzka et al., 2017) all fail to converge to the optimal f * (x) in many of our synthetic experiments. We thus developed a new method for enforcing k-Lipschitz and we found in our experiments that the new method stably converges to the optimal f * (x). Figure 18 : Comparison between gradient penalty and maximum gradient penalty, with P r and P g consist of ten real and noise images, respectively. The leftmost in each row is a x ∼ P g and the second is its gradient ∇ x f * (x). The interior are x + • ∇ x f * (x) with increasing , which will pass through a real sample, and the rightmost is the corresponding y ∼ P r .

The new method. Note that the practical methods of imposing k-Lipschitz is not the key contribution of this work, and it is far from well-validated. We plan a further work on this topic for a more rigorous study. But for the necessity for understanding our paper and reproducing of experiments, we introduce it as follows.

Combining the idea of spectral normalization and gradient penalty, we developed an new regularization for Lipschitz continuity in our experiments. Spectral normalization is actually constraining the maximum gradient over the entire space. And as we argued previously, enforcing Lipschitz continuity in the blending region is sufficient. Therefore, we propose to restricting the maximum gradient over the blending region:

EQUATION

In practice, we sample x from training batch as in (Gulrajani et al., 2017; Petzka et al., 2017) . To improve the stability and reduce the biased introduced via batch sampling, we propose the keep track x with the maximum ∇f (x) 2 . A practical and light weight method is to maintain a list S max that has the currently highest (top-k) ∇f (x) 2 (initialized with random x samples), using the S max as part of the batch estimation of J maxgp , and update the S max after each batch updating of the discriminator. In our experiment, S max takes 1/2 batch, and the remaining 1/2 batch are random sampled. S max always keeps track of the maximal 1/2 samples in the batch.

We compare the practical result of gradient penalty E x∼B [ ∇f (x)

2 2 ] and the proposed maximum gradient penalty in Figure 18 . Before switching to maximum gradient penalty, we struggled for a long time and cannot achieve a high quality result as showed in Figure 18b . The other forms of gradient penalty (Gulrajani et al., 2017; Petzka et al., 2017) 

perform similar as E x∼B [ ∇f (x) 2 2 ]. F DISCUSSION ON NO-DIFFERENTIABLE f * (x) If f * (x) is k-Lipschitz and f * (y) -f * (x) = k • d(x,

y), we say that (x, y) are coupled. When a sample x is coupled with more than one y and these y lie in different directions of x, f * (x) is non-differentiable at x and it will has sub-gradient along each direction.

When the f * (x) non-differentiable, due to the smoothness of practically-used neural network, as we noticed in the experiments, it usually behaviors as that the gradient direction is pointing in the middle of these sub-gradient (more strictly, a linear combination of these sub-gradients).

It seems that when the P g is discrete (simulating discrete token generation, such as language and music), it is easy to become non-differentiable: in the optimal transport perspective, once it is required to move to more than one targets, f * (x) is non-differentiable at this point.

One way to alleviate this above problem is adding noise (e.g. Gaussian) to each discrete token from P g . The discrete token with different noises now disperse to different targets. In the practical generator for continuous token, such as images, this kind of non-differentiable problem naturally get solved.

The more serious non-differentiable problem traces back to the Monge problem (Villani, 2008) , which theoretically discussed under which condition the optimal transport is a one-one mapping, which by nature solve the non-differentiable problem, as each sample now has a single target.

However, for the Monge problem is solvable, i.e. the mapping from P g and P r is one-one, it requires the d(x, y) to be a strictly convex and super-linear (Villani, 2008) . Unfortunately, the Euclidean distance, which is necessary to ensure the gradient direction from fake sample directly points toward real sample, does not fit this condition. So we currently does not figure out a practical solution to take advantage of the Monge problem related theories.

Nonetheless, even if f * (x) is non-differentiable, the gradient is also usually somehow pointing towards the real samples. And the empirical founding is that: when the P g get close to P r , the non-differentiable problem diminishes.

G PROOF OF THE THEOREM 1:

Let J D = E x∼Pg [φ(f (x))] + E x∼Pr [ϕ(f (x))] = P g (x)φ(f (x)) + P r (x)ϕ(f (x))dx. Let ∂ x J D denotes P g (x)φ(f (x)) + P r (x)ϕ(f (x)). It has J D = ∂ x J D dx. Define J = J D +λ•k(f ) 2 , where k(f ) is Lipschitz constant of f (x) . Let f * (x) = arg min f [J D +λ• k(f ) 2 ]. Let J * D (k) = min f ∈Fk-Lip J D = min f ∈F1-Lip,b E x∼Pg [φ(k•f (x)+b)]+E x∼Pr [ϕ(k•f (x)+b)]. Lemma 1. ∀x, ∂[∂xJ D ] ∂f * (x) = 0 if and only if k(f * ) = 0.

Proof.

(i) ∀x, ∂[∂xJ D ] ∂f * (x) = 0 implies k(f * ) = 0.

For the optimal f * (x), it holds that ∂J ∂k(f

* ) = ∂J * D ∂k(f * ) + 2λ • k(f * ) = 0. ∀x, ∂[∂xJ D ] ∂f * (x) = 0 implies ∂J * D ∂k(f * ) = 0. We thus conclude that k(f * ) = 0. (ii) k(f * ) = 0 implies ∀x, ∂[∂xJ D ] ∂f * (x) = 0.

For the optimal f * (x), it holds that ∂J ∂k(f

* ) = ∂J * D ∂k(f * ) + 2λ • k(f * ) = 0. So k(f * ) = 0 implies ∂J * D ∂k(f * ) = 0. k(f * ) = 0 also implies ∀x, y, f * (x) = f * (y).

If there exists some point x such that

∂[∂xJ D ] ∂f * (x) = 0, then, given ∀x, y, f * (x) = f * (y), it is obviously that ∂J * D ∂k(f * ) = 0. It is contradictory to ∂J * D ∂k(f * ) = 0. Thus we has ∀x, ∂[∂xJ D ] ∂f * (x) = 0. Lemma 2. If ∀x, y, f * (x) = f * (y), then P g = P r . Proof. ∀x, y, f * (x) = f * (y) implies k(f * ) = 0. According to Lemma 1, ∀x, ∂[∂xJ D ] ∂f * (x) = P g (x) ∂φ(f * (x)) ∂f * (x) +P r (x) ∂ϕ(f * (x)) ∂f * (x) = 0. So Pg(x) Pr(x) = - ∂ϕ(f * (x)) ∂f * (x) ∂φ(f * (x)) ∂f * (x)

, and thus

Pg(x)

Pr(x) has a constant value, which straightforwardly implies P g = P r .

Proof of Theorem 1.

(i) Considering the f * (x), ∀x ∈ Pg ∪ Pr , if there does not exist a y such that

|f * (y) -f * (x)| = k(f * ) • d(x, y), because f * (x) is the optimal, it must hold that ∂[∂xJ D ]

∂f * (x) = 0.4 (ii) For x ∈ Pg ∪ Pr -Pg ∩ Pr , assuming P g (x) = 0 and P r (x) = 0, we have

∂[∂xJ D ] ∂f * (x) = P g (x) ∂φ(f * (x)) ∂f * (x) + P r (x) ∂ϕ(f * (x)) ∂f * (x) = P g (x) ∂φ(f * (x))

∂f * (x) > 0, because P g (x) > 0 and ∂φ(f * (x)) ∂f * (x) > 0. Then, according to (i), there must exist a y such that |f * (y) -f * (x)| = k(f * ) • d(x, y). The other situation can be proved in the same way.

(iii) According to Lemma 2, in this situation that P g = P r , for the optimal f * (x), there must exist at least one pair of points x and y such that x = y and f * (x) = f * (y). If there are no x and y satisfying that |f * (y) -f * (x)| = k(f * ) • d(x, y), it will be contradictory to that f * (x) is optimal, because we can construct a better f * by decreasing the value of k(f ) until there are two points, e.g. (iv) In Nash Equilibrium state, it holds that, for any

x ∈ Pg ∪ Pr , ∂J ∂k(f ) = ∂J * D ∂k(f ) + 2λ • k(f ) = 0 and ∂[∂xJ D ] ∂f (x)

∂f (x) ∂x = 0. We claim that in the Nash Equilibrium state, the Lipschitz constant k(f ) must be 0. If k(f ) = 0, according to Lemma 1, there must exist a point x such that ∂[∂ x J D ] ∂f (x) = 0. And according to (i), it must hold that ∃ŷ fitting |f

(ŷ) -f (x)| = k(f ) • d(x, ŷ). According to Theorem 3, we have ∂f (x) ∂x x=x 2 = k(f ) = 0. This is contradictory to that ∂[∂xJ D ] ∂f (x) ∂f (x)

∂x x=x = 0. Thus k(f ) = 0, that is, ∀x ∈ Pg ∪ Pr , ∂f (x) ∂x = 0, which means ∀x, y, f (x) = f (y). According to Lemma 2, ∀x, y, f (x) = f (y) implies P g = P r . Thus P g = P r is the only Nash Equilibrium of our system.

Remark: For the Wasserstein distance, ∂[∂xJ D ] ∂f * (x) = 0 if and only if P g (x) = P r (x). For the Wasserstein distance, penalizing the Lipschitz constant also benefits: at the convergence state, it holds ∂f * (x) ∂x = 0.

H ON THE IMPORTANCE OF EQ. 12

Requiring φ(x) and ϕ(x) to satisfy Eq. 12 is important, because it is the non-trivial condition that makes sure

E x∼Pg [φ(f (x))] + E x∼Pr [ϕ(f (x))] + λ • k(f ) 2

has attainable global minimum with respect to f .

Theorem 5. If φ(x) and ϕ(x) satisfies Eq. 12, then for any fixed P g and P r ,

E x∼Pg [φ(f (x))] + E x∼Pr [ϕ(f (x))] + λ • k(f ) 2

has an lower bound with respect to f .

Proof.:

Given ∃a, φ (a) + ϕ (a) = 0, φ (x) ≥ 0 and ϕ (x) ≥ 0, we have:

E x∼Pg [φ(f (x))] + E x∼Pr [ϕ(f (x))] + λ • k(f ) 2 ≥ E x∼Pg [φ (a)(f (x) -a) + φ(a)] + E x∼Pr [ϕ (a)(f (x) -a) + ϕ(a)] + λ • k(f ) 2 = E x∼Pg [φ (a)f (x)] + E x∼Pr [ϕ (a)f (x)] + λ • k(f ) 2 + c = φ (a)[E x∼Pg [f (x)] -E x∼Pr [f (x)]] + λ • k(f ) 2 + c ≥ φ (a)[k • -W 1 (P r , P g )] + λ • k 2 + c = [-φ (a)W 1 (P r , P g )] • k + λ • k 2 + c ≥ c - [φ (a)W 1 (P r , P g )] 2 4λ Remark. Theorem 5 implies that there exists an infimum for E x∼Pg [φ(f (x))]+E x∼Pr [ϕ(f (x))]+ λ • k(f ) 2 . According to the definition of infimum, there exists a sequence of {f n } ∞ n=1 such that E x∼Pg [φ(f n (x))] + E x∼Pr [ϕ(f n (x))] + λ • k(f n ) 2 infinitely approaches the infimum. Remark. The Lipschitz constant of f n , i.e., k(f n ), as n goes to infinity, is bounded, because E x∼Pg [φ(f (x))] + E x∼Pr [ϕ(f (x))] + λ • k(f ) 2 > [-φ (a)W 1 (P r , P g )] • k(f ) + λ • k(f ) 2 + c.

We further present several simply Lemmas. These Lemmas and their proofs would provide some intuitive impressions on why Eq. 12 is necessary and the properties of proposed objectives.

Lemma 3. Assuming P g and P r are two delta distributions. If φ(x) and ϕ(x) satisfies Eq. 12, then for any fixed P g and P

r , E x∼Pg [φ(f (x))] + E x∼Pr [ϕ(f (x))

] has global minimum with respect to f , for any fixed k(f ) = k.

Proof. Given P g and P r are two delta distributions, according to Theorem 1 and Theorem 2, for x ∼ P g and y

∼ P r , f * (y) -f * (x) = k • d(x, y). Let f * (x) = α and β = k • d(x, y), then f * (y) = α + β. Define J D (α) = E x∼Pg [φ(f (x))] + E x∼Pr [ϕ(f (x))] = φ(α) + ϕ(α + β).

Given ∃ a such that φ (a) + ϕ (a) = 0, φ (x) ≥ 0 and ϕ (x) ≥ 0, we have, when α is small enough (such that, α < a and α+β < a), J D (α) = φ (α)+ϕ (α+β) ≤ φ (a)+ϕ (a) = 0. Similarly, when α is large enough (such that, α > a and α+β > a), J D (α) = φ (α)+ϕ (α+β) ≥ φ (a)+ϕ (a) = 0. Therefore, J D (α) is convex with respect to α and there exists an α 0 such that J D (α 0 ) = 0, where J D achieves its the global minimum. When φ (x) > 0 and ϕ (x) > 0, it is the unique global minimum.

Lemma 4. Assuming P g and P r are two delta distributions. If φ(x) and ϕ(x) satisfies Eq. 12, then for any fixed P g and P r , E x∼Pg [φ(f (x))] + E x∼Pr [ϕ(f (x))] monotonically increases as k(f ) decreases.

Proof. Given P g and P r are two delta distributions, according to Theorem 1 and Theorem 2, for x ∼ P g and y

∼ P r , f * (y)-f * (x) = k•d(x, y). Let f * (x) = α and β = k•d(x, y) > 0, then f * (y) = α + β. Define J D (β) = min f ∈Fk-Lip E x∼Pg [φ(f (x))] + E x∼Pr [ϕ(f (x))] = min α φ(α) + ϕ(α + β).

We need to prove J D (β) is monotonically decreasing, for β ≥ 0.

Let 0 ≤ β 1 < β 2 , let α 1 = min α φ(α) + ϕ(α + β 1 ) and α 2 = min α φ(α) + ϕ(α + β 2 ). Given ϕ (x) < 0 and β 1 < β 2 , we have φ(α 1 ) + ϕ(α 1 + β 1 ) > φ(α 1 ) + ϕ(α 1 + β 2 ). Given α 2 = min α φ(α) + ϕ(α + β 2 ), we further have φ(α 1 ) + ϕ(α 1 + β 1 ) > φ(α 1 ) + ϕ(α 1 + β 2 ) ≥ φ(α 2 ) + ϕ(α 2 + β 2 ). Done. Additionally, with φ (α 1 ) + ϕ (α 1 + β 1 ) = 0 and ϕ (x) ≥ 0, we have φ (α 1 ) + ϕ (α 1 + β 2 ) ≥ 0. Providing φ (α 2 ) + ϕ (α 2 + β 2 ) = 0, φ (x) ≥ 0 and ϕ (x) ≥ 0, we get α 2 ≤ α 1 . That is, α 2 ≤ α 1 < β 1 < β 2 . When φ (x) > 0 and ϕ (x) > 0, we have α 2 < α 1 < β 1 < β 2 .

Lemma 5. If the support of P g and P r is bounded, i.e., ∃R such that x < R, ∀x ∈ Pg ∪ Pr . Assume φ(x) and ϕ(x) satisfy Eq. 12 and further have φ 

(x) > 0 or ϕ (x) > 0. ∀N , ∃M , if E x∼Pg [φ(f (x))] + E x∼Pr [ϕ(f (x))] + λ • k(f ) 2 < N , then |f (x)| < M, ∀x ∈ Pg ∪ Pr . Proof. ∃a, φ (a) + ϕ (a) = 0 and φ (x) + ϕ (x) > 0 implies ∃b, φ (b) + ϕ (b) > 0. Then: E x∼Pg [φ(f (x))] + E x∼Pr [ϕ(f (x))] + λ • k(f ) 2 ≥ E x∼Pg [φ (b)(f (x) -b) + φ(b)] + E x∼Pr [ϕ (b)(f (x) -b) + ϕ(b)] + λ • k(f ) 2 = E x∼Pg [φ (b)f (x)] + E x∼Pr [ϕ (b)f (x)] + λ • k(f ) 2 + c = [φ (b) + ϕ (b)]E x∼Pg [f (x)] + ϕ (b)[E x∼Pr [f (x)] -E x∼Pg [f (x)]] + λ • k(f ) 2 + c ≥ [φ (b) + ϕ (b)]E x∼Pg [f (x)] + ϕ (b)[W 1 (P r , P g ) • k(f )] + λ • k(f ) 2 + c ∀x ∈ Pg ∪ Pr , if f (x) = T , then: ∀x ∈ Pg ∪ Pr , f (x) ≥ T -k(f ) • R. E x∼Pg [φ(f (x))] + E x∼Pr [ϕ(f (x))] + λ • k(f ) 2 ≥ [φ (b) + ϕ (b)](T -k(f ) • R) + ϕ (b)[W 1 (P r , P g ) • k(f )] + λ • k(f ) 2 + c ≥ [

where Π(P r , P g ) denotes the collection of all probability measures with marginals P r and P g on the first and second factors respectively.

The dual form of Wasserstein distance is usually written as:

I(P r , P g ) = sup f E x∼Pr [f (x)] -E x∼Pg [f (x)],

s.t. f (x) -f (y) ≤ d(x, y), ∀x, ∀y.

(20)

We will prove that Wasserstein distance in its dual form can also be written as:

J(P r , P g ) = sup f E x∼Pr [f (x)] -E x∼Pg [f (x)],

s.t. f (x) -f (y) ≤ d(x, y), ∀x ∼ P r , ∀y ∼ P g ,

which means the constraint in the dual form of Wasserstein distance can be looser than the common formulation.

With the compacted formulation, we argued that a well-defined metric, i.e., J(P r , P g ), which is equivalent to Wasserstein distance W 1 (P r , P g ) and thus can properly measure the distance between two distributions, may also fail to provide a meaningful ∇ x f * (x). This observation indicates that a well-defined distance metric does not necessarily guarantee a meaningful ∇ x f * (x) and thus does not guarantee the convergence of ∇ x f * (x)-based GANs.

I.1 PROVING THE EQUIVALENCE Theorem 6. Given I(P r , P g ) = W 1 (P r , P g )5 , we have I(P r , P g ) = J(P r , P g ) = W 1 (P r , P g )

Proof.

(i) For any f that satisfies "f (x) -f (y) ≤ d(x, y), ∀x, ∀y", it must satisfy "f (x) -f (y) ≤ d(x, y), ∀x ∼ P r , ∀y ∼ P g ". Thus, I(P r , P g ) ≤ J(P r , P g ).

(ii) Let F J = {f | f (x) -f (y) ≤ d(x, y), ∀x ∼ P r , ∀y ∼ P g }.

Let A = {(x, y)|x ∼ P r , y ∼ P g } and I A = 1, (x, y) ∈ A; 0, otherwise .

Let A c denote the complementary set of A and define I A c accordingly.

∀π ∈ Π(P r , P g ) We have the following: (iii) Combining (i) and (ii), we have I(P r , P g ) ≤ J(P r , P g ) ≤ W 1 (P r , P g ). Given I(P r , P g ) = W 1 (P r , P g ), we have I(P r , P g ) = J(P r , P g ) = W 1 (P r , P g ).

J(P r , P g ) = sup f ∈F J E x∼Pr [f (x)] -E x∼Pg [f (x)] = sup f ∈F J E (x,

I.2 PROVING J(P r , P g ) = W 1 (P r , P g ) DIRECTLY Let Pr and Pg denote the supports of P r and P g , respectively. Because ∀π ∈ Π(P r , P g ), it must hold that π(x, y) = 0 for any (x, y) that outside Pr × Pg , i.e., P r (x) = 0 or P g (y) = 0 implies π(x, y) = 0. We let Γ( Pr × Pg ) denote the collection of all probability measures that defined on Pr × Pg with marginals P r and P g on the first and second factors respectively. Let M + ( Pr × Pg ) be the collection of all non-negative measures (not necessarily probability measures) on Pr × Pg .

Before the proof, we would like to give several preliminary notes.

• A more formal and detailed proof for Kantorovich duality with same logic of justification can be found in Theorem 2.3 of (Zemel, 2012) . And a more relevant version that focused on Wasserstein distance can be found in this blog6 .

• The key change here is that we handle the support of P r and P g more carefully, which results in elimination of the unnecessary constraints f (x) -f (y) ≤ d(x, y) that involve (x, y) pair where P r (x) = 0 or P g (x) = 0.

• The validity of the use of the minimax-principle, i.e., invert the order of inf and sup, in this case, is proved in (Zemel, 2012) and the blog.

Theorem 7. J(P r , P g ) = W 1 (P r , P g )

Proof. 

I.3 ANOTHER PERSPECTIVE: ELIMINATING REDUNDANT CONSTRAINT:

To provide a more comprehensive understanding on why constraint f (x) -f (y) ≤ d(x, y) that involves point (x, y) where P r (x) = 0 or P g (x) = 0 is unnecessary, we here give a intuitive explanation in the following way: one can safely remove all constraints that does not involve any point in the support of P g and P r , because give f (x) -f (y) ≤ d(x, y), ∀x ∼ P r , ∀y ∼ P g , it is sufficient to bound the value of f (x) for x ∼ P r and f (y) for y ∼ P g . In other words, given the existence of constraint f (x) -f (y) ≤ d(x, y), ∀x ∼ P r , ∀y ∼ P g , the other constraints can be safely eliminated without affecting the final solution.

:

In this paper, traditional GANs mainly refers to the original GAN and Least-Squares GAN, where f * (x) depends only on the densities Pg(x) and Pr(x). Broadly, it refers to all GANs where f * (x) does not reflect information about the locations of the other points in Pg and Pr, such as the Fisher GAN.

Here and later, "two distributions are disjoint" means that their supports are disjoint.

Actually, we argue that the distance metrics must be Euclidean distance in GANs. See Appendix D.

Otherwise, as f * (x) is not constrained by the Lipschitz constraint, we can construct a better f * by adjusting the value of f * (x) at x according to the non-zero gradient.

The equivalence of W1(Pr, Pg) and I(Pr, Pg) is well-known(Villani, 2008;Zemel, 2012).

https://vincentherrmann.github.io/blog/wasserstein/

Figures and Tables:

Figure1: In traditional GANs, f * (x) is only defined on the supports of P g and P r and its values do not reflect any information about the locations of other points in P g and P r . Therefore, they have no guarantee on the convergence. Wasserstein distance in a compacted dual form suffers from the same problem. GANs under Lipschitz constraint builds connection between P g and P r , where ∇ x f * (x) pulls P g towards P r .

Figure2: The source of Mode Collapse. In traditional GANs, f * (x) is a function of the local densities P g (x) and P r (x). Given f * (x) is an increasing function of P r (x) and decreasing function of P g (x), when fake samples get close to a mode of the P r , ∇ x f * (x) move them towards the mode.

Figure 3: Verifying the objective family Figure 4: ∇ x f * (x) gradation with CIFAR-10

Figure 5: f * (x) in new objective is more stable.

Figure7: ADAM optimizer with lr=1e-2, beta1=0.0, beta2=0.9. MLP with RELU activations, #hidden units=1024, #layers=1.

Figure8: ADAM optimizer with lr=1e-2, beta1=0.0, beta2=0.9. MLP with RELU activations, #hidden units=1024, #layers=4.

Figure 10: SGD optimizer with lr=1e-3. MLP with SELU activations, #hidden units=128, #lay-ers=64.

Figure 11: SGD optimizer with lr=1e-4. MLP with SELU activations, #hidden units=128, #lay-ers=64.

Figure12: Various φ(x) and ϕ(x) that satisfies Eq. 12.

Figure 14: Random Samples of Lipschitz GAN trained of different objectives on Oxford 102.

Figure 15: Random Samples of Lipschitz GAN trained of different objectives on Cifar-10.

Figure 16: Random Samples of Lipschitz GAN trained of different objectives on Tiny Imagenet.

Figure17: The gradient of Lipschitz constraint based GANs with real world data, where P r consists of ten images and P g is Gaussian noise. Up: Each odd column are x ∼ P g and the nearby column are their gradient ∇ x f * (x). Down: the leftmost in each row are x ∼ P g , the second are their gradients ∇ x f * (x), the interior are x + • ∇ x f * (x) with increasing , and the rightmost are the nearest y ∼ P r .

x and y, constrained by Lipschitz constraint, i.e. |f * (y) -f * (x)| = k(f * ) • d(x, y).

φ (b) + ϕ (b)]T -[ϕ (b)W 1 (P r , P g ) -[φ (b) + ϕ (b)]R] 2 4λ + c Given E x∼Pg [φ(f (x))] + E x∼Pr [ϕ(f (x))] + λ • k(f ) 2 < N , we have: [φ (b) + ϕ (b)]T -[ϕ (b)W 1 (P r , P g ) -[φ (b) + ϕ (b)]R] 2 4λ + c < N ⇒ T < (N -c + [ϕ (b)W 1 (P r , P g ) -[φ (b) + ϕ (b)]R] 2 4λ )/[φ (b) + ϕ (b)]Similarly, ∃a, φ (a) + ϕ (a) = 0 and φ (x) + ϕ (x) > 0 implies ∃d, φ (d) + ϕ (d) < 0. And then it implies T is greater than some constant. So, ∃M such that |f (x)| < M, ∀x ∈ Pg ∪ Pr .I PROOF ON THE DUAL FORM OF WASSERSTEIN DISTANCEWe here provide a formal proof for our new dual form of Wasserstein distance. The Wasserstein distance is given as follows:W 1 (P r , P g ) = inf π∈Π(Pr,Pg) E (x,y)∼π[d(x, y)],

y)∼π [f (x) -f (y)] = sup f ∈F J E (x,y)∼π [(f (x) -f (y))I A ] + E (x,y)∼π [(f (x) -f (y))I A c ] = sup f ∈F J E (x,y)∼π [(f (x) -f (y))I A ] ≤ E (x,y)∼π [d(x, y)I A ] ≤ E (x,y)∼π [d(x, y)].J(P r , P g ) ≤ E (x,y)∼π [d(x, y)], ∀π ∈ Π(P r , P g ) ⇒ J(P r , P g ) ≤ inf π∈Π(Pr,Pg) E (x,y)∼π [d(x, y)] = W 1 (P r , P g ).

s∼Pr [f (s)] -E t∼Pg [f (t)] -Pr Pg (f (x) -f (y))π(x, y)dxdy = inf π∈M+( Pr× Pg) sup f E s∼Pr [f (s)] -E t∼Pg [f (t)] + Pr Pg [d(x, y) -(f (x) -f (y))]π(x, y)dxdy = sup f inf π∈M+( Pr× Pg) E s∼Pr [f (s)] -E t∼Pg [f (t)] + Pr Pg [d(x, y) -(f (x) -f (y))]π(x, y)dxdy = sup f E s∼Pr [f (s)] -E t∼Pg [f (t)] + inf π∈M+( Pr× Pg) Pr Pg [d(x, y) -(f (x) -f (y))]π(x, y)dxdy = sup f E s∼Pr [f (s)] -E t∼Pg [f (t)] + 0, f (x) -f (y) ≤ d(x, y), ∀x ∼ P r , ∀y ∼ P g -∞, otherwise = sup f E s∼Pr [f (s)] -E t∼Pg [f (t)], s.t. f (x) -f(y) ≤ d(x, y), ∀x ∼ P r , ∀y ∼ P g .

Quantitative comparisons on unsupervised image generation tasks.

Table content: <table><tr><td>Objective</td><td>FID</td><td colspan="2">CIFAR-10</td><td>IS</td><td colspan="2">Tiny ImageNet FID</td><td>IS</td><td>Oxford 102 Flower FID* IS*</td></tr><tr><td>-min(0, -x -1)</td><td colspan="2">21.58 ± 0.21</td><td colspan="2">7.43 ± 0.04</td><td colspan="3">16.22 ± 0.33 8.58 ± 0.08 9.72 ± 0.51</td><td>21.91 ± 0.18</td></tr><tr><td>x</td><td colspan="2">19.64 ± 0.23</td><td colspan="2">7.66 ± 0.03</td><td>18.81 ± 0.58</td><td colspan="2">8.20 ± 0.05</td><td>9.74 ± 0.63</td><td>21.66 ± 0.22</td></tr><tr><td>-log(σ(-x)) x + √ x 2 + 1</td><td colspan="7">16.36 ± 0.09 8.49 ± 0.11 15.94 ± 0.33 8.42 ± 0.04 15.76 ± 0.13 8.04 ± 0.04 16.83 ± 0.41 8.35 ± 0.09 9.16 ± 0.52 21.96 ± 0.19 9.40 ± 0.49 21.82 ± 0.11</td></tr><tr><td>exp(x)</td><td colspan="2">19.82 ± 0.13</td><td colspan="2">7.79 ± 0.03</td><td>20.45 ± 0.15</td><td colspan="2">8.06 ± 0.05</td><td>9.90 ± 0.72</td><td>21.91 ± 0.22</td></tr><tr><td>-log(σ(-x)) + 0.01x</td><td colspan="2">18.32 ± 0.15</td><td colspan="2">7.75 ± 0.04</td><td>16.09 ± 0.23</td><td colspan="2">8.47 ± 0.10</td><td>9.50 ± 0.39</td><td>21.91 ± 0.20</td></tr></table>

Peer review (iclr2019):
 The authors try to claim that Lipschitz continuity of the discriminator is a fundamental solution of GANs, and that current methods do not satisfy this approach in principle. There are several false statements in this paper. In particular, sections 2.3 and 4.4 are wrong (and most of the paper is based on statements made there). The necessary constraint for the Wasserstein distance is NOT f(x) - f(y) <= d(x, y) for all x ~ Pr, y ~ Pg. It has to actually be 1-Lipschitz in the entire space. See Chapters 5 and 6 of [1], for example remark 6.4 or particular cases 5.16 and 5.4. Indeed, this is how it is written in all of the literature this reviewer is aware off, and it*s a fact well used in the literature. Indeed, all the smoothness results for optimal transport in [1] heavily exploit the fact that the gradient of the critic is in the direction of the optimal transport map, which wouldn*t be the case in the situation the authors try to claim of *f not being defined outside of the support of Pr or Pg*. Furthermore, the relationship between Lipschitz continuity and having a gradient is elaborated in [2] https://arxiv.org/abs/1701.07875 , for example figure 2 clearly show this. Furthermore, and contrary to what section 4.5 tries to claim, the idea that most conclusions of wgan hold *without* the Wasserstein distance, but with Lipschitz continuity are already elaborated in the wgan paper. See in fact, appendix G.1 [3], where this is described in detail. [1]: http://cedricvillani.org/wp-content/uploads/2012/08/preprint-1.pdf [2]: http://proceedings.mlr.press/v70/arjovsky17a/arjovsky17a.pdf [3]: http://proceedings.mlr.press/v70/arjovsky17a/arjovsky17a-supp.pdf