What is Lipschitz constraint and why it is enforced on discriminator?

Question

The following is the abstract for the research paper titled Improved Training of Wasserstein GANs

Generative Adversarial Networks (GANs) are powerful generative models, but suffer from training instability. The recently proposed Wasserstein GAN (WGAN) makes progress toward stable training of GANs, but sometimes can still generate only poor samples or fail to converge. We find that these problems are often due to the use of weight clipping in WGAN to enforce a Lipschitz constraint on the critic, which can lead to undesired behavior. We propose an alternative to clipping weights: penalize the norm of gradient of the critic with respect to its input. Our proposed method performs better than standard WGAN and enables stable training of a wide variety of GAN architectures with almost no hyperparameter tuning, including 101-layer ResNets and language models with continuous generators. We also achieve high quality generations on CIFAR-10 and LSUN bedrooms.

Here, the critic stands for discriminator of the GAN. I understood that the discriminator must obey Lipschitz constraint and hence weight clipping is generally done before this paper. The paper provides an alternative way, penalizing the norm of the gradient of the critic with respect to its input, to enforce the desired Lipschitz constraint.

What actually is Lipschitz constraint and why is it mandatory for a discriminator to obey it?

Answer 1

The Lipschitz constraint is essentially that a function must have a maximum gradient. The specific maximum gradient is a hyperparameter.

It's not mandatory for a discriminator to obey a Lipschitz constraint. However, in the WGAN paper they find that if the discriminator does obey a Lipschitz constraint, the GAN works much better.

A perfect discriminator would perfectly accept all the real samples (output=1 with low gradient) and perfectly reject all the fake samples (output=0 with low gradient), but this provides hardly any gradient information to help train the generator. By limiting the gradient of the discriminator, they force it to be a worse discriminator, but provide more gradient information which helps train the generator.

You can see this in figure 2 (page 9) of the WGAN paper. The red line is a good discriminator but its gradient is nearly 0 at most points. The cyan line (which for some reason is presented upside-down) is clearly much worse as a discriminator, but is much better for training the generator because its gradient is not zero.

The way they limit the discriminator's overall gradient in the WGAN paper is by separately limiting (clipping) each of the weights in the discriminator. They are aware this is a "terrible" idea, and leave better ideas for further research. The paper you are asking about is one of those better ideas.

Note that since back-propagation works backwards, enforcing a maximum gradient (Lipschitz continuity) on the discriminator in the forward direction causes it to have a minimum gradient in the backward direction, which is what we want when training the generator.

Answer 2

Optimizing a traditional GAN is equivalent to minimizing KL-divergence, which is known to have limitations. Wasserstein metric promises to remedy these limitations, and is defined as follows:

$$ W(P_r, P_g) = \inf_{\gamma \in \prod(P_r ,P_g)} \mathbb{E}_{(x, y) \sim \gamma}\big[\:\|x - y\|\:\big] $$

However, computing $\prod(P_r, P_g)$ for all possible joint probability distributions is extremely intractable. Thus the authors proposed a smart transformation of the formula based on the Kantorovich-Rubinstein duality, defined as:

$$ W(P_r, P_\theta) = \sup_{\|f\|_L \leq K} \mathbb{E}_{x \sim P_r}[f(x)] - \mathbb{E}_{x \sim P_\theta}[f(x)] $$

For this to work, $\| f \|_L \leq K$ must hold, which means that $f$ must be K-Lipschitz continuous. $f$ is called K-Lipschitz continuous if there exists a real constant $K \geq 0$ such that, for all $x_1, x_2 \in \mathbb{R}$,

$$\lvert f(x_1) - f(x_2) \rvert \leq K \lvert x_1 - x_2 \rvert$$ ​ Here $K$ is known as a Lipschitz constant for the function $f$. Lipschitz continuity ensures that the derivative of $f$ is less than or equal to K everywhere (or to 1 for 1-Lipschitz). This can be illustrated as follows:

For a Lipschitz continuous function, there exists a double cone (white) whose origin can be moved along the graph so that the whole graph always stays outside the double cone

Thus, we have a parametrized family of functions $\{f_w\}_{w \in W}$ that are all K-Lipschitz for some $K$. The function $f$ has the role of a non-linear feature map that maximally enhances the differences between the samples coming from the two distributions. The role of the Lipschitz constraint is to prevent $f$ from arbitrarily enhancing small differences. The constraint assures that if two input images are similar the output of $f$ will be similar as well. Without this constraint, the result would be zero when $P_r$ is equal to $P_g$ and $\infty$ otherwise, since the effect of any minor difference can be arbitrarily enhanced by an appropriate feature map.

The supremum over $K$-Lipschitz functions is still intractable, but now $\{f_w\}$ can be approximated using a neural network. For optimization purposes, it is not necessary to know what $K$ is. It is enough to know that it exists and that it is fixed throughout the training process (read this article for more details).