How Well Can Generative Adversarial Networks Learn Densities: A Nonparametric View

Introduction

Generative Adversarial Networks (GANs) (Goodfellow et al., 2014; Li et al., 2015; Arjovsky et al., 2017; Dziugaite et al., 2015) have stood out as an important unsupervised method for learning and efficient sampling from a complicated, multi-modal target data distribution. Despite its celebrated empirical success in image tasks, there are many theoretical questions to be answered (Liu et al., 2017; Arora and Zhang, 2017; Arora et al., 2017a).

One convenient formulation of the GAN framework (Arjovsky et al., 2017; Li et al., 2015; Dziugaite et al., 2015; Liu et al., 2017) solves the following minimax problem, at the population level,

In plain language, given a target distribution $\nu$, one seeks for a distribution $\mu$ from a probability distribution generator class $\mu_{G}$, such that it minimizes the loss incurred by the best discriminator function inside the discriminator class $\mathcal{F}_{D}$. In practice, both the generator class and the discriminator class are represented by neural networks. $\mu_{G}$ quantifies the transformed distributions realized by a network with random inputs (either Gaussian or uniform distribution), and $\mathcal{F}_{D}$ represents the functions that are realizable by a certain neural network architecture. We refer the readers to Liu et al. (2017) for other more general formulations of GANs.

Two fundamental yet basic questions that puzzle machine learning theorists are: (1) how well does GAN learn the densities statistically, overlooking the optimization difficulty? (2) how well does the iterative optimization dynamics of solving the minimax problem approximate the optimal solution?

In the statistics literature, density estimation has been a central topic in nonparametric statistics (Nemirovski, 2000; Tsybakov, 2009; Wassermann, 2006). The minimax optimal rate of convergence has been understood fairly well, for a wide range of density function classes quantified by its smoothness. We would like to point out a simple yet convincing connection between two fields: in nonparametric statistics, the model grows in size to accommodate the complexity of the data, which is reminiscent of the model complexity in GANs, and more generally in the deep neural networks.

Note the GAN framework mentioned above is flexible. Define the following metric induced by the function class $\mathcal{F}$,

If $\mathcal{F}$ contains all Lipschitz-$1$ functions, then $d_{\mathcal{F}}(\mu,\nu)$ is the Wasserstein-1 metric (Wasserstein-GAN (Arjovsky et al., 2017)). When $\mathcal{F}$ represents all functions bounded by $1$, then $d_{\mathcal{F}}(\mu,\nu)$ is the total variation metric (Radon metric). Let $\mathcal{H}$ be a reproducing kernel Hilbert space (RKHS) and $k(\cdot,\cdot)$ be its kernel. If $\mathcal{F}$ consists of functions in the closure of the span of the set $\{k(\cdot,x),x\in\Omega\}$, then $d_{\mathcal{F}}(\mu,\nu)=\|d(\mu-\nu)/dx\|_{\mathcal{H}}$ (MMD-GAN (Dziugaite et al., 2015; Li et al., 2015)).

Consider the density function that lies in Sobolev space with smoothness parameter $\alpha$

and the discriminator function class $\mathcal{F}_{D}=W^{\beta,2}(L)$ with smoothness $\beta$. As $\alpha,\beta$ varies, $\mathcal{F}_{R}$ describes a wide range of nonparametric densities, and $\mathcal{F}_{D}$ provides a rich hierarchy of critic metrics. Let $n$ be the sample size, $d$ be the dimension.

In contrast, as long as $\alpha>\frac{\beta}{d/(2\beta)-1}$, the GAN estimator $\hat{\mu}_{n}$ with empirical measure $\hat{\nu}_{n}$ only achieves a considerably slower rate

Nonparametric estimation with GAN framework. The GAN framework for nonparametric density estimation enjoys the upper bound

One may wonder whether this rate can be significantly improved by other approaches. We show that for any procedure $\nu_{n}$ based on $n$ samples, the minimax lower bound under the metric $d_{\mathcal{F}_{D}}$ reads

In the case when $d$ is large, the exponent in the upper bound and the minimax lower bounds are very close to each other, in the sense that $\frac{\alpha+\beta}{2\alpha+d}=(1+\mathcal{O}(1/d))\frac{\alpha+\beta}{2(\alpha+\beta)+d}$.

In the case when both the generator and discriminator are realized by neural networks. We establish the following results using the insights gained from above.

Networks can learn densities. We make progress on answering how well generative adversarial networks learn nonparametric densities $d\nu(x)/dx\in W^{\alpha,\infty}(L)$ with smoothness parameter $\alpha$, under the Wasserstein metric.

In addition, for all estimators $\nu_{n}$ based on $n$ samples, the minimax rate cannot be smaller than

Here $C,c>0$ are constants independent of $n$. Note that by Yarotsky (2017), one can approximate $W^{k,\infty}(1)$ within $\epsilon$ accuracy by ReLU networks with $\log(1/\epsilon)$ depth and $\text{poly}(1/\epsilon)$ units for integer $k$. The formal and more general statment can be found in Thm. 3.1.

2 Preliminaries

For integer $k$, define the Sobolev space $W^{k,p}(L)$ ($p=2,\infty$)

where $\alpha$ is a multi-index and $D^{(\alpha)}$ denotes the $\alpha$-weak derivative.

Another equivalent definition of Sobolev space for $p=2$ is through the coefficients of the generalized Fourier series, which is also referred to as the Sobolev ellipsoid.

A nonparametric view of the GAN framework

The following oracle inequality holds for GAN.

Let $\mathcal{F}$ be any critic function class. Denote $\mu_{n}$ as the solution (w.r.t. the empirical estimate $\nu_{n}$) to GAN with generator $\mu_{G}$ and discriminator $\mathcal{F}_{D}$

Then the following decompositions hold for any distribution $\nu$,

Let’s remark on the decompositions. Eqn. (2.1) use $d_{\mathcal{F}_{D}}$ as the objective evaluation metric. The first term is the best approximation error within the generator class, even if we have population access to the true measure $\nu$. The second term is the statistical error, also called the generalization error, due to the fact that we have only finite $n$-samples. Eqn. (2.2) employs a different $d_{\mathcal{F}}$ as the objective metric, while using the mis-matched discriminator class $\mathcal{F}_{D}$ in the GAN procedure. The first term describes the approximation error induced by the generator, the second term corresponds to how well the discriminator serves as a surrogate for the objective metric, and the third term is the statistical error.

Using the above theorem, choose $\mathcal{F}_{D}$ as the critic metric, we need to study the excess loss

We will start with a crude bound when $d\nu_{n}(x)/dx=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_{i}}(x)$ is chosen as the empirical density. It turns out that one can significantly improve this bound through choosing a better “regularized” or “smoothed” version of empirical measure, in the context of learning nonparametric densities. The empirical measure is not optimal because one can leverage the complexity/smoothness of the measure $\nu$, and the complexity of $\mathcal{F}_{D}$ to improve upon the generalization error.

2 Upper bound for arbitrary density

Take $d\hat{\nu}_{n}(x)/dx=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_{i}}(x)$, then

Assuming $\sup_{f\in\mathcal{F}_{D}}\|f\|_{\infty}\leq 1$, one has the standard entropy integral bound,

Plugging in the entropy estimate $\log\mathcal{N}(\epsilon,\mathcal{F}_{D},\|\cdot\|_{\infty})$ for various functional classes (Nickl and Pötscher (2007) and reference therein), one can easily derive the following corollary.

It is easy to see that overlooking the distributional information — by simply going through symmetrization and empirical processes theory — can lead to suboptimal result when the true density is smooth. Roughly speaking, the symmetrization approach treats the true density as a highly non-smooth one with $\alpha=0$ (say the empirical density). Next, we will investigate how to improve GAN when the true density lies in Sobolev spaces $W^{\alpha,2}(L),\alpha>0$.

3 Smoothness helps: improved upper bound for Sobolev spaces

Now we show that one can achieve faster rates in the GAN framework for density estimation, simultaneously leveraging the smoothness information in the density $d\nu$ and the metric $\mathcal{F}_{D}$.

Consider the density function class that lies in Sobolev space with smoothness parameter $\alpha$, and the discriminator function class with smoothness $\beta$,

Theorem 2.1 tells us the rate of convergence satisfies the following upper bound

this nonparametric upper bound achieves a faster rate than the symmetrization bound which ignores the smoothness of the distribution. Remark in the real applications of GAN, the dimension $d$ is rather large (in images usually $d>10^{3}$), and $\beta$ is fairly small for a strong metric ($\beta=1$ in Wasserstein GAN), so this condition is satisfied for any $\alpha>0.002$. In summary, we write out the explicit rate of convergence,

Let’s broaden the discussions slightly by considering different base measures $\pi(x)$ beyond the Lebesgue measure, and the generalized Fourier basis. One can think of $\pi(x)$ as the uniform measure on $^{d}$ or the product Gaussian measure. An equivalent formulation of the GAN problem that translates learning a distribution $d\mu(x)=g(x)d\pi(x)$ to learning the importance score/density ratio function $g(x)$ with respect to a base measure $\pi(x),x\in\mathcal{X}$, can be viewed as

Assume the generalized Fourier basis are bounded $\max_{\xi}\|\psi_{\xi}(x)\|_{\infty}\leq C$. Consider the density function class with smoothness $\alpha$, and the discriminator function class $\mathcal{F}_{D}$ with smoothness $\beta$

4 Minimax lower bound

Can the rate obtained by GAN framework be significantly improved by any other procedure? We consider in this section the minimax lower bound for the intrinsic difficulty of nonparametric estimation under the GAN discriminator metric. Here we consider a nonparametric function estimation problem on the Sobolev ellipsoid $\Theta^{\alpha}(L)$, which is statistically equivalent to the density estimation problem over the Sobolev space $W^{\alpha,2}(L)$ asymptotically (Tsybakov, 2009). A separate lower bound for the density estimation within the smaller Hölder class $W^{\alpha,\infty}(L)$ is proved in Thm. 3.1.

Consider the function class with smoothness $\alpha$ and the discriminator function class $\mathcal{F}_{D}$ with smoothness $\beta$

In the Gaussian sequence model (2.4), for any estimator $\nu_{n}$,

Let us compare our lower bound with the upper bound in Remark 2.1. When the generator function class is rich enough so that $\mu_{G}$ contains the $\nu$, the upper bound becomes

Remark again, when take as a special case the base measure $\pi(x)$ being uniform on $^{d}$, $\mathcal{F}_{R}=W^{\alpha,2}(L)$ and $\mathcal{F}_{D}=W^{\beta,2}(L)$ are the usual Sobolev spaces. In the case when $d$ is large, the exponents in the upper and lower bounds are very close to each other, in the sense that $\frac{\alpha+\beta}{2\alpha+d}=(1+o_{d}(1))\frac{\alpha+\beta}{2(\alpha+\beta)+d}$.

How well networks learn densities

In this section, we answer in a quantitative way that when both the generator class and the discriminator class represented by deep ReLU networks are rich enough, one do learn the distribution. One can view our results as establishing rate of convergence and fundamental difficulty for learning the distribution under the GAN framework, for a wide range of densities with different smoothness properties. It builds a more detailed theory upon the seminal work of Goodfellow et al. (2014), where they proved that when sample sizes, generator sizes, and discriminator sizes are all infinite, one learns the distribution.

Let’s remark on the universal approximation property of deep networks first before introducing the result. It is well known that deep neural networks are universal approximators (Hornik et al., 1989). In particular, Yarotsky (2017) constructed a fixed ReLU network architecture, denoted as $\mathcal{F}_{relu}^{\alpha}(\epsilon)$, that enjoys the following two properties:

It approximates all functions in $W^{\beta,\infty}(1)$ in the following sense

It has depth at most $\mathcal{O}(\log 1/\epsilon)$ and at most $\mathcal{O}(\epsilon^{-d/\beta}\log 1/\epsilon)$ weights and computation units.

With the above in mind, we are ready to state the following theorem.

The discriminator network class can approximate the Sobolev space $W^{\beta,\infty}(1)$, in the sense that $\max_{f\in W^{\beta,\infty}(1)}\min_{f^{\prime}\in\mathcal{F}_{D}}\|f-f^{\prime}\|_{\infty}\leq\epsilon$;

The generator network class can approximate the Sobolev space $\nu\in W^{\alpha,\infty}(L)$, in the sense that for any true density $d\nu/dx\in W^{\alpha,\infty}(L)$, $\min_{\mu\in\mu_{G}}\|\mu-\nu\|_{\infty}\leq\epsilon$;

The discriminator network class is not overly complex in the sense that $\mathcal{F}_{D}\subset W^{\beta,2}(L)\cap W^{0,\infty}(M)$. In other words, the weak derivatives are integrable and the function is bounded.

In addition, the minimax lower bound for any estimator $\nu_{n}$ based on $n$ samples satisfies,

Here $C_{i},i=1,2,3$ are constants independent of $n$.

Note the lower bound here is harder than that in Theorem 2.3 because: (1) the class is in fact Hölder (subset of the Sobolev), $W^{\alpha,\infty}(L)\subset W^{\alpha,2}(L)$, (2) for density estimation directly.

Let us make few remarks on the objective metrics and rates here. When $\beta=1$, the objective metric is equivalent to the Wasserstein-$1$ metric (Lemma 4.2). Therefore with properly chosen discriminator and generator network GAN enjoys the upper bound $n^{-\frac{\alpha+1}{2\alpha+2+d}}$, while the minimax lower bound being $n^{-\frac{\alpha+1}{2\alpha+d}}$. Consider the following two scenarios:

When the dimension $d$ is very large, for a fixed smoothness parameter $\alpha$, these two rates are very close. In this case, to obtain an $\epsilon$-error in Wasserstein metric, GAN requires exponential number of samples (in dimension) $n=\epsilon^{-(2+\frac{d}{\alpha+1})}$, so does any other procedure as indicated by the lower bound.

When the the smoothness parameter scales with the dimension, say $\alpha+1\geq d/C_{0}$ for some constant $C_{0}>0$, then GAN only requires a polynomial number of samples $n=\epsilon^{-(2+C_{0})}$. In the large dimension setting when $d\rightarrow\infty$, any other procedure will require at least $n=\epsilon^{-(2+C_{0})}$ as well.

Let us comment on the assumptions used in the theorem. We consider the function class realized by ReLU networks. Define $c(\alpha,\beta,d)=\frac{\alpha+\beta}{2(\alpha+\beta)+d}\vee(\frac{\beta}{d}\wedge\frac{1}{2})$ and let’s choose $\epsilon\asymp n^{-c(\alpha,\beta,d)}$.

The assumption A.1 on the discriminator network class can be realized by subsuming a specific fixed architecture (Yarotsky, 2017) as a subclass $\mathcal{F}_{D}\supseteq\mathcal{F}_{relu}^{\beta,\infty}(\epsilon)$, where the network $\mathcal{F}_{relu}^{\beta,\infty}(\epsilon)$ has depth $\mathcal{O}(c(\alpha,\beta,d)\log n)$, and $\mathcal{O}^{*}(n^{\frac{d}{\beta}c(\alpha,\beta,d)})$ weights and computational units. Roughly, this means that one may need a deep discriminator network (scales logarithmically with number of samples in depth, and polynomially in number of units) to recover the density in a strong sense such as under the Wasserstein metric.

The assumption A.2 on the generative network class can also be realized if we reformulate the GAN in an importance sampling way: given uniform samples $X\in^{d}$, the generative network outputs a importance/density score $\mu(X)$ realized by function realized by the network. Again, the deep network $\mu_{G}\supseteq\mathcal{F}_{relu}^{\beta,\infty}(\epsilon)$ with depth $\mathcal{O}(c(\alpha,\beta,d)\log n)$ and $\mathcal{O}^{*}(n^{\frac{d}{\beta}c(\alpha,\beta,d)})$ weights does the job. Note in practice, the generative network learns a transformation of $X$ with $\mu(X)$ as the density, instead of assigning the importance score. We do acknowledge that learning the transformation mapping (represented by the network) from the input random measure to the target measure has computational advantage over the importance sampling approach. However, overlooking the computation, output an importance score is also plausible to learn a distribution theoretically.

The assumption A.3 can be relaxed. In fact, one can prove a variant of the theorem without assumption 3, in the sense

It formalizes the intuition that if we choose a too strict metric as the discriminator ($\mathcal{F}_{D}$ too rich), even though we are evaluating on a weaker metric (induced by a smaller function space $W^{\beta,\infty}(1)$), there is a price to pay in the rates for choosing the overly complex space $\mathcal{F}_{D}$ as discriminator.

2 Error rates for deeper ReLU discriminator networks

In the GAN formulation, the discriminator class $\mathcal{F}_{D}$ is represented by functions realized by a neural network with a certain architecture. In this section, we will apply our theory to obtain bounds for a wide range of feed-forward multi-layer networks with ReLU activation as the discriminator metric.

Denote $\sigma(x)=\max(x,0)$ as the ReLU activation. Consider the following feed-forward multi-layer network:

There is constant $V\geq 1$ such that for each unit in the network, the vector $w$ of weights associated with that unit has $\|w\|_{1}\leq V$.

Mathematically, one can define the function class induced by the network through the recursive definition: $\mathcal{F}^{(0)}(V)=\{x\rightarrow x_{i}:x=(x_{1},\ldots,x_{d})\in^{d},i\in[d]\}\cup\{0,1\}$, and for any $i\geq 1$,

Let’s remark on how our bound improves upon what is known, and when one can improve GAN by using a better estimate than the empirical measure $\hat{\nu}_{n}$.

Recall the covering number bound (Thm. 14.17) for deeper networks in Anthony and Bartlett (2009), one knows that

More concretely, consider the following two extreme scenarios:

Technical Proofs

For any $\mu\in\mu_{G}$, we know that due to the optimality of GAN

where we use the following fact $d_{\mathcal{F}}(\mu_{1},\mu_{2})+d_{\mathcal{F}}(\mu_{2},\mu_{3})\geq d_{\mathcal{F}}(\mu_{1},\mu_{3})$ and

It is easy to bound the following using similar logic

This matches the best known bound as in Canas and Rosasco (2012) (Section 2.1.1).

Remark in addition that the parametric rate $\frac{1}{\sqrt{n}}$ is inevitable, which can be easily seen from the Sudakov minoration,

where based on i.i.d. samples $X^{(1)},X^{(2)},\ldots X^{(n)}\sim\nu$

For any $\nu\in\mathcal{F}_{R}$ (or equivalently $g\in W^{\alpha,2}(L_{\alpha})$), we have

For the second term, the following inequality holds

Combining two terms, we have for any $\nu\in\mathcal{F}_{R}$ (or equivalently $g\in W^{\alpha,2}(L)$),

And the optimal choice of $M\asymp n^{\frac{1}{2(\alpha+\beta)+d}}$. Note that this is a more aggressive smoothing scheme than classic nonparametric estimation with smoothness $\alpha$, due to the fact that we are utilizing the smoothness in the evaluation metric at the same time.

The proof uses the standard Fano’s inequality.

Assume that $H\geq 2$ and suppose $\Theta$ contains $\theta_{0},\theta_{1},\ldots,\theta_{H}$ such that:

$d(\theta_{j},\theta_{k})\geq 2s>0$, for all $j,k\in[H]$ and $j\neq k$.

$\frac{1}{H}\sum_{j=1}^{H}D_{\rm KL}(P_{j},P_{0})\leq\alpha\log H$ with $0<\alpha<1/8$ and $P_{j}=P_{\theta_{j}}$ for $j\in[H]$.

Let’s construct a mixture of hypothesis on the function space $W^{\alpha,2}(L)$, and a subset of discriminator functions in $W^{\beta,2}(L)$, such that the multiple testing problem among the mixture of hypothesis is hard, and thus the loss induced by the best discriminator among the subset provides a lower bound on the estimation rate. Let’s construct this mixture in the frequency domain. Choose $M>0$ to be determined later, denote the hypothesis class of interest to be

It is easy to verify that $\Omega_{\alpha}\subset W^{\alpha,2}(L)$ because for any $g_{w}(x)$, we have

Similarly, let’s consider $\Lambda_{\beta}\subset W^{\beta,2}(L)$

where $\rho(w,w^{\prime})$ denotes the Hamming distance between $w$ and $w^{\prime}$ on the hypercube $\{0,1\}^{M^{d}}$. Now we need to construct a subset over the hypercube such that for any pairs $w,w^{\prime}$, they are separated in terms of Hamming distance.

The Varshamov-Gilbert bound (Lemma 2.9 in Tsybakov (2009)) does the job. We know that there exist a subset $\{w^{(0)},\ldots,w^{(H)}\}\subset\{0,1\}^{h}$ such that $w^{(0)}=(0,\ldots,0)$,

Now let’s calculate the probability distance $P_{j},P_{0}$ induced by hypothesis $w^{(j)}$ and $w^{(0)}$, for all $j\in[H]$ to show that information theoretically, it is hard to distinguish the mixture of hypothesis. The following holds,

If we choose $M=\left(\frac{4L^{2}}{c\log 2}\frac{1}{d^{\alpha}}\right)^{\frac{1}{2\alpha+d}}\cdot n^{\frac{1}{2\alpha+d}}$, we know

We outline the key steps of the proof. Due to the approximation property of the network class $\mathcal{F}_{D}$ to $W^{\beta,\infty}(1)$, and $\mu_{G}$ to $W^{\alpha,\infty}(1)$, we know that

because $F_{D}\subseteq W^{0,\infty}(M)$. Apply the oracle inequality (2.2), one has

Here the last step we use the following fact

Therefore for any $\nu\in W^{\alpha,\infty}(1)$,

where the last line follows from Theorem 2.2. Combine with the approximation error, we reach

Under the assumption that $\mathcal{F}_{D}\subseteq W^{\beta,2}(L)$, then

and $\|(g_{w}(x)-g_{0}(x))/g_{w}(x)\|_{\infty}\leq c_{w}+a^{d}h_{n}^{\alpha}\ll 1/50$. It is easy to verify (1) $\Omega_{\alpha}\subset W^{\alpha,\infty}(L)$ for some $L$, and each element in the set is a valid density; (2) $\Lambda_{\beta}\subset W^{\beta,\infty}(1)$, as for any multi-index $\gamma$,

To apply the Fano’s Lemma, let’s first show that the hypothesis are separated in the evaluation metric. Let’s use the same subset $\{w^{(0)},\ldots,w^{(H)}\}\subset\{0,1\}^{h}$ claimed by the Varshamov-Gilbert bound

In our case $h=m^{d}$. For the loss function, any $w,w^{\prime}\in\{w^{0},\ldots,w^{H}\}$

Now let’s show that based $n$ i.i.d. data generated from density $g_{w}(x)$, it is hard to distinguish the hypothesis. Note that for $|x|<1/50$, we know that $\log(1+x)\geq x-x^{2}$. Therefore

Therefore if we choose $m\asymp n^{-\frac{1}{2\alpha+d}}$, we know $\frac{1}{H}\sum_{j=1}^{H}D_{\rm KL}(P_{w^{(j)}}^{\otimes n},P_{w^{(0)}}^{\otimes n})\leq c\log H=c^{\prime}m^{d}$. Using the Fano’s Lemma, the lower bound for density estimation is of the order $h_{n}^{\alpha+\beta}=n^{-\frac{\alpha+\beta}{2\alpha+d}}$, as

Without loss of generality assume the function is differentiable. Then

Observe that $\|x-y\|_{1}\geq\|x-y\|_{2}\geq\|x-y\|_{\infty}$. Then $|f(x)-f(y)|\leq L\|x-y\|_{\infty}\leq L\|x-y\|_{2}\leq L\|x-y\|_{1}$. For the other side of the inequality, $\|x-y\|_{1}\leq\sqrt{d}\|x-y\|_{2}\leq d\|x-y\|_{\infty}$, hence $|f(x)-f(y)|\leq L\|x-y\|_{1}\leq L\sqrt{d}\|x-y\|_{2}\leq Ld\|x-y\|_{\infty}$. ∎

Acknowledgement

The author thanks Sasha Rakhlin for helpful discussions.

References