Minimax Optimality (Probably) Doesn't Imply Distribution Learning for
  GANs
  Arguably the most fundamental question in the theory of generative
adversarial networks (GANs) is to understand to what extent GANs can actually
learn the underlying distribution. Theoretical and empirical evidence suggests
local optimality of the empirical training objective is insufficient. Yet, it
does not rule out the possibility that achieving a true population minimax
optimal solution might imply distribution learning.
  In this paper, we show that standard cryptographic assumptions imply that
this stronger condition is still insufficient. Namely, we show that if local
pseudorandom generators (PRGs) exist, then for a large family of natural
continuous target distributions, there are ReLU network generators of constant
depth and polynomial size which take Gaussian random seeds so that (i) the
output is far in Wasserstein distance from the target distribution, but (ii) no
polynomially large Lipschitz discriminator ReLU network can detect this. This
implies that even achieving a population minimax optimal solution to the
Wasserstein GAN objective is likely insufficient for distribution learning in
the usual statistical sense. Our techniques reveal a deep connection between
GANs and PRGs, which we believe will lead to further insights into the
computational landscape of GANs.
