On some theoretical limitations of Generative Adversarial Networks

The universal approximation property of neural networks (see [8] and [4]) might make us assume that GANs can simulate any distribution from a Gaussian prior. However, neural networks, as functions are by design almost everywhere differentiable functions with bounded derivatives to limit exploding gradients phenomenons (see [10]). By Rademacher (see [7] for a proof) and mean value theorems, this is nearly equivalent to say that neural networks functions are Lipschitz continuous. This fact basically sets the limitations of GANs to express any probability distribution given a Gaussian prior. The are numerous definitions of the concept of ”fat”, ”longed” or ”heavy” tailed distributions. They are usually not equivalent but all convey a sense of having a larger probability of being ”big” compared to a Gaussian or Exponential distribution. Here we focus on two possible ways to define the concept. One, similarly to [12], is focussing on finite samples and relies on classical concentration inequalities. The other is asymptotic and uses Extreme Value Theory to prove a new theorem in the continuity of the theoretical work of Huster et al. in [9] and the experimental approach of [6].

Notations, in the following, we make use of the following notations:

• -

  $f$ is a Lipschitz function $\mathbb{R}^{n}\mapsto\mathbb{R}$, $||f||_{l}=\sup_{x,y\in\mathbb{R}^{n},x\neq y}\frac{||f(x)-f(y)||}{||x-y||}$ its semi-norm,

• -

  $\gamma_{n}$ the Gaussian measure on $\mathbb{R}^{n}$,

• -

  $d$ the Euclidean distance in $\mathbb{R}^{n}$ i.e. $d(x,y)=||y-x||$,

• -

  for any set $S\subset\mathbb{R}^{n}$ the $\epsilon$ neighbourhood $S_{\epsilon}=\{x\in\mathbb{R}^{n}\text{ such that }d(x,S)<\epsilon\}$, where $\epsilon>0$,

• -

  $\bar{A}$ the complement of a subset $A\subset\mathbb{R}^{n}$,

• -

  $M$ the median of a mapping $\mathbb{R}^{n}\mapsto\mathbb{R}$ for the $\gamma_{n}$ measure i.e. $\gamma_{n}(\{f\geq M\})\geq\frac{1}{2}$ and $\gamma_{n}(\{f\leq M\})\geq\frac{1}{2}$,

• -

  $X$ a standard Gaussian random variable in $\mathbb{R}^{n}$,

• -

  $\bar{\Psi}=\frac{1}{\sqrt{2\pi}}\int_{x}^{+\infty}e^{-u^{2}/2}du$ the Gaussian tail function.

In this section we prove that given a Lipschitz function and a Gaussian prior $X$, $f(X)$ is sub-gaussian: a GAN with a Gaussian prior can only generate sub-gaussian distributions.

For a proof see [15].

If $G=f(X)$, where $f$ is Lipschitz, by Lipschitz continuity and $\mathbb{E}(X)=0$

In particular if $X$ is one dimensional then using a standard upper bound of the gaussian tail function $G$ will be sub-gaussian as a sum of two independant sub-gaussian functions, considering $f(0)$ as a constant random variable.

If $X$ was $n$ dimensional then,

and $|X|^{2}$ following a $\chi^{2}$ distribution with $n$ degrees of freedom the sub-gaussianity of $G$ would seem to be dependent on the dimension of $X$. Yet, this is not the case as stated by the following remarkable result:

So in particular, a GAN with a Gaussian prior will not be able to generate any realistic samples even if trained on a ”fat tailed” distribution. This is not the first time that concentration of measure gives some strong theoretical limits to machine learning methods see [5] or [11] for a more recent paper. Limitations of GANs has also been explored from a different perspective in [16].

This theorem is also true when we replace the mean $\mathbb{E}(f(X))$ by a median of $f(X)$. The original proof of the theorem can be found in [14]. The proof is quite technical, a more accessible one can be found in [2] . To get a sense of the concentration of measure phenomenon we provide here a simple proof with the median.

The gaussian concentration theorem is a consequence of:

It is easily seen that $\gamma_{n}(H_{r})=\Psi(a+r)$ where $\Psi$ is the cumulative distributive function of the one dimensional standard Gaussian distribution.
It is not obvious at first sight what is the link between this theorem and the Gaussian concentration theorem for Lipschitz functions. The link is made defining the following ‘isoperimetric function’ for $a\in[0,1]$ and $\epsilon>0$

We can now prove the Gaussian concentration theorem.

In this section, we prove the main result of this paper: given a Lipschitz function and a Gaussian prior $X$, if $f(X)$ is in a domain of attraction of an extreme value distribution of parameter $\xi$ then $\xi\leq 0$. In particular, $f(X)$ can’t be ”heavy tailed”. In fact, we prove the theorem for a wider range of distributions.
In the following, we use the notations of Extreme Value Theory that are introduced in [9].

Because of the intrinsic Lipschitz characteristics of Neural Networks, GANs expressivity is limited. In particular, a Gaussian prior cannot be used to simulate heavy tailed distributions. In the EVT framework, the question of the existence of a tail index for the generated distribution, or the conditions for its existence, remains. A theoretical partial answer is given in [9] for GANs with ReLU or Leaky-ReLU activation functions and a finite number of neurons. The general case is still an open question. Likewise, determining the thinnest tail prior being able to simulate samples exhibiting heavy tails is an important question needing further investigations.
Moreover, experimentally, the problem of training GANs with a heavy-tailed prior remains too. Indeed, with such priors GANs are hard to train and exhibit numerical instabilities.