A GAN without Lipschitz Constraints and Vanishing Gradients: Introducing GAN-QP

Basic Definition

Let’s first look at the discriminator loss in SGAN, defined as: \mathcal{D}[p(x), q(x)] = \max_T \frac{1}{2}\mathbb{E}_{x \sim p(x)}[\log \sigma(T(x))] + \frac{1}{2}\mathbb{E}_{x \sim q(x)}[\log (1 - \sigma(T(x)))] + \log 2 \label{eq:js-dual-2} This is actually the dual form of the JS divergence. However, we can prove it is a divergence directly based on this definition and discuss its properties without even knowing it is the JS divergence.

How to prove it? We only need to prove that this result satisfies the two requirements of a divergence mentioned above. Note that according to our logic, we don’t know it’s JS divergence, but we can prove it’s a divergence from a mathematical perspective.

If the reader truly understands the meaning of Equation [eq:js-dual-2], the proof is not difficult. Equation [eq:js-dual-2] first defines an expectation formula and then takes the maximum over T (more accurately, the "supremum"). Only the result of taking the maximum is the divergence. To emphasize again: "the result after taking the maximum is the divergence"; the expression \frac{1}{2}\mathbb{E}_{x \sim p(x)}[\log \sigma(T(x))] + \frac{1}{2}\mathbb{E}_{x \sim q(x)}[\log (1 - \sigma(T(x)))] + \log 2 itself is not a divergence.

The specific proof process is somewhat lengthy and won’t be fully presented here; please refer to the appendix of the original paper. Alternatively, look at the WGAN section below, as it is relatively simpler.

Adversarial Networks

Once we have a divergence, we can train a generative model by minimizing the divergence between two probability distributions. That is, the next step is: \min_{G} \mathcal{D}[p(x), q(x)] Note that \mathcal{D}[p(x), q(x)] is achieved through the \max_T operation, so the combination is a min-max process. For the previous example, this is equivalent to: G, T = \mathop{\text{argmin}}_G \mathop{\text{argmax}}_T \mathbb{E}_{x \sim p(x)}[\log \sigma(T(x))] + \mathbb{E}_{x=G(z), z \sim q(z)}[\log (1 - \sigma(T(x)))] \label{eq:js-min-max} This is SGAN.

So we find that the GAN process actually consists of two steps: 1. Define a divergence through \max; 2. Minimize the divergence between two distributions through \min. The new perspective here is to treat \max directly as part of the definition of the divergence.

Performance Analysis

We know that SGAN may suffer from the risk of vanishing gradients. Why is this? Let’s examine an extreme case: p(x) = \delta(x - \alpha), \quad q(x) = \delta(x - \beta) where \alpha \neq \beta. In this case, the two distributions are just single-point distributions with no overlap. Substituting this into [eq:js-dual-2], the result is: \mathcal{D}[p(x), q(x)] = \max_T \frac{1}{2}[\log \sigma(T(\alpha))] + \frac{1}{2}[\log (1 - \sigma(T(\beta)))] + \log 2 Since we have no constraints on T, to maximize this, we can let T(\alpha) \to +\infty and T(\beta) \to -\infty, resulting in a supremum that is the constant \log 2. That is, in this case, \mathcal{D}[p(x), q(x)] = \log 2.

This means that for two distributions with almost no overlap, the divergence defined by Equation [eq:js-dual-2] yields a constant \log 2. A constant means the gradient is 0, making optimization impossible. The two WGAN papers showed that "no overlap" is theoretically very common in GANs, so this is an inherent flaw of SGAN.

General f-divergences

The previous subsections have fully presented the workflow of this understanding:

1. We define a mathematical expression through \max, and then prove from a mathematical perspective that it is a divergence, without caring what it is called;

2. We minimize this divergence through \min, and the combination is a min-max process, resulting in a type of GAN;

3. To check the performance of this divergence in extreme cases, we can test it with p(x) = \delta(x - \alpha), q(x) = \delta(x - \beta).

The above discussion regarding SGAN can be extended in parallel to all f-GANs. Various f-divergences are not essentially different; they share the same inherent flaws (either vanishing gradients or exploding gradients).

Basic Definition

Now we turn to a new class of divergence: Wasserstein distance. Note that Wasserstein distance is a strict distance satisfying axiomatic definitions, but here we only care about its divergence properties. Define: \mathcal{W}[p(x), q(x)] = \max_{T, \|T\|_L \leq 1} \mathbb{E}_{x \sim p(x)}[T(x)] - \mathbb{E}_{x \sim q(x)}[T(x)] \label{eq:wd-dual} where \|T\|_L = \max_{x \neq y} \frac{|T(x) - T(y)|}{d(x, y)} and d(x, y) is any existing distance.

It can be directly proven to be a divergence. This proof is quite classic, so I will write it here:

1. Regardless of p(x) and q(x), if we let T(x) \equiv 0, we get \mathbb{E}_{x \sim p(x)}[T(x)] - \mathbb{E}_{x \sim q(x)}[T(x)] = 0. Since the definition of divergence requires taking the maximum over all T, it will at least not be less than 0. This proves the first point (non-negativity).

2. Prove that when p(x) = q(x), \mathcal{W}[p(x), q(x)] = 0. This is almost self-evident.

3. Prove that when p(x) \neq q(x) (strictly speaking, the measure where they are unequal is greater than 0), \mathcal{W}[p(x), q(x)] > 0. This is relatively harder but still simple. Just let T_0(x) = \text{sign}(p(x) - q(x)), then clearly: \begin{aligned} &\mathbb{E}_{x \sim p(x)}[T_0(x)] - \mathbb{E}_{x \sim q(x)}[T_0(x)] \\ =& \int (p(x) - q(x)) \cdot \text{sign}(p(x) - q(x)) dx > 0 \end{aligned}

Thus, we directly prove that \mathcal{W}[p(x), q(x)] satisfies the definition of a divergence.

Adversarial Networks

Similarly, with a new divergence, we can define a new GAN: G, T = \mathop{\text{argmin}}_G \mathop{\text{argmax}}_{T, \|T\|_L \leq 1} \mathbb{E}_{x \sim p(x)}[T(x)] - \mathbb{E}_{x=G(z), z \sim q(z)}[T(x)] \label{eq:wd-min-max} This is WGAN.

Performance Analysis

Similarly, testing the performance of the \mathcal{W}[p(x), q(x)] divergence with p(x) = \delta(x - \alpha), q(x) = \delta(x - \beta), we get: \mathcal{W}[p(x), q(x)] = \max_{T, \|T\|_L \leq 1} T(\alpha) - T(\beta) Note that we have the L-constraint \|T\|_L \leq 1, which means |T(\alpha) - T(\beta)| \leq d(\alpha, \beta). The equality can be achieved, so: \mathcal{W}[p(x), q(x)] = d(\alpha, \beta) The result is not a constant, so even in this extreme case, we can pull the two distributions closer. From this point of view, WGAN is better than SGAN.

L-constraints

The legacy issue of WGAN is how to add the L-constraint to the discriminator. Currently, there are three schemes: weight clipping, gradient penalty, and spectral normalization.

Weight clipping has basically been abandoned. Gradient penalty is in principle just an empirical method with its own irrationalities, and calculating gradients is usually slow. Spectral normalization seems the most elegant and currently performs well, though it has the possibility of being too restrictive.

Basic Definition

The divergence to be presented below takes the following form: \begin{aligned} &\mathcal{L}[p(x), q(x)] \\ =& \max_{T} \mathbb{E}_{(x_r, x_f) \sim p(x_r)q(x_f)} \left[ T(x_r, x_f) - T(x_f, x_r) - \frac{(T(x_r, x_f) - T(x_f, x_r))^2}{2\lambda d(x_r, x_f)} \right] \end{aligned} \label{eq:qp-dual} where \lambda > 0 is a hyperparameter, and d can be any distance.

This form looks like adding a quadratic potential energy term on top of WGAN, so it is called Quadratic Potential Divergence (QP-div).

The appendix of the paper proves that Equation [eq:qp-dual] is indeed a divergence.

Performance Analysis

Testing this divergence with p(x) = \delta(x - \alpha), q(x) = \delta(x - \beta), the result is: \mathcal{L}[p(x), q(x)] = \max_{T} T(\alpha, \beta) - T(\beta, \alpha) - \frac{(T(\alpha, \beta) - T(\beta, \alpha))^2}{2\lambda d(\alpha, \beta)} Let z = T(\alpha, \beta) - T(\beta, \alpha), then we get z - \frac{z^2}{2\lambda d(\alpha, \beta)}. Does this look familiar? This is just a maximum value problem for a quadratic function! The maximum value is \frac{1}{2}\lambda d(\alpha, \beta), so we have: \mathcal{L}[p(x), q(x)] = \frac{1}{2}\lambda d(\alpha, \beta) This is similar to WGAN; even for extreme distributions, there is no risk of vanishing gradients. You really can have both.

Adversarial Networks

With the divergence, we can construct an adversarial network. The final form we provide is: \begin{aligned} &T = \mathop{\text{argmax}}_T \mathbb{E}_{(x_r, x_f) \sim p(x_r)q(x_f)} \left[ T(x_r, x_f) - T(x_f, x_r) - \frac{(T(x_r, x_f) - T(x_f, x_r))^2}{2\lambda d(x_r, x_f)} \right] \\ &G = \mathop{\text{argmin}}_G \mathbb{E}_{(x_r, x_f) \sim p(x_r)q(x_f)} \left[ T(x_r, x_f) - T(x_f, x_r) \right] \end{aligned} \label{eq:gan-gp-gd} I call this GAN-QP in the paper.

Note: do not include the quadratic term -\frac{(T(x_r, x_f) - T(x_f, x_r))^2}{2\lambda d(x_r, x_f)} in the generator’s loss. (Theoretically, it’s not a problem, but there will be issues when optimizing with gradient descent.) Because the denominator of this term is d(x_r, x_f), minimizing the quadratic term would be equivalent to minimizing d(x_r, x_f), which means using d(x_r, x_f) to measure the gap between images, which is unscientific.

Analysis of the Solution

Using the calculus of variations, it can be proven (also in the appendix) that the optimal solution for the discriminator is: \frac{p(x_r)q(x_f) - p(x_f)q(x_r)}{p(x_r)q(x_f) + p(x_f)q(x_r)} = \frac{T(x_r, x_f) - T(x_f, x_r)}{\lambda d(x_r, x_f)} \label{eq:opt-t}

From this optimal solution, we can draw two conclusions. First, it is not difficult to prove that the optimal solution satisfies: -1 \leq \frac{T(x_r, x_f) - T(x_f, x_r)}{\lambda d(x_r, x_f)} \leq 1 In other words, the optimal solution automatically satisfies the L-constraint. Therefore, we can consider GAN-QP as an adaptive L-constraint scheme.

Secondly, substituting the optimal solution into the generator’s loss, the total objective becomes: \lambda \iint p(x_r)q(x_f) \frac{p(x_r)q(x_f) - p(x_f)q(x_r)}{p(x_r)q(x_f) + p(x_f)q(x_r)} d(x_r, x_f) dx_r dx_f This is also a probability divergence, and we have theoretically proven that it will not suffer from vanishing/exploding gradients (related to the Cauchy-Schwarz inequality). Furthermore, we can see that \lambda is just a scaling factor and is not actually important. Consequently, GAN-QP is robust to \lambda, and \lambda does not significantly affect the model’s performance.