# Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs

arXiv: https://arxiv.org/abs/2201.07206 · HTML: https://mlsanity.com/paper/2201.07206/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 52 references that are in the map.
- First posted on arXiv 18 Jan 2022.

## Builds on (most cited first, 25 of 25)

- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [A Review on Generative Adversarial Networks: Algorithms, Theory, and Applications](https://mlsanity.com/paper/2001.06937/) (2020)
- [Generalization and Equilibrium in Generative Adversarial Nets (GANs)](https://mlsanity.com/paper/1703.00573/) (2017)
- [Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review](https://mlsanity.com/paper/1611.00740/) (2016)
- [How Well Generative Adversarial Networks Learn Distributions](https://mlsanity.com/paper/1811.03179/) (2018)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [Stabilizing Generative Adversarial Networks: A Survey](https://mlsanity.com/paper/1910.00927/) (2019)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [On the Discrimination-Generalization Tradeoff in GANs](https://mlsanity.com/paper/1711.02771/) (2017)
- [Approximation and Convergence Properties of Generative Adversarial Learning](https://mlsanity.com/paper/1705.08991/) (2017)
- [Approximability of Discriminators Implies Diversity in GANs](https://mlsanity.com/paper/1806.10586/) (2018)
- [Statistical guarantees for generative models without domination](https://mlsanity.com/paper/2010.09237/) (2020)
- [Nonparametric Density Estimation under Adversarial Losses](https://mlsanity.com/paper/1805.08836/) (2018)
- [Learning Deep ReLU Networks Is Fixed-Parameter Tractable](https://mlsanity.com/paper/2009.13512/) (2020)
- [A Closer Look at the Optimization Landscapes of Generative Adversarial Networks](https://mlsanity.com/paper/1906.04848/) (2019)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [Nonparametric Density Estimation & Convergence Rates for GANs under Besov IPM Losses](https://mlsanity.com/paper/1902.03511/) (2019)
- [Complexity theoretic limitations on learning DNF's](https://mlsanity.com/paper/1404.3378/) (2014)
- [From average case complexity to improper learning complexity](https://mlsanity.com/paper/1311.2272/) (2013)
- [SGD Learns One-Layer Networks in WGANs](https://mlsanity.com/paper/1910.07030/) (2019)
- [On the Complexity of Random Satisfiability Problems with Planted Solutions](https://mlsanity.com/paper/1311.4821/) (2013)
- [Understanding GANs: the LQG Setting](https://mlsanity.com/paper/1710.10793/) (2017)
- [Indistinguishability Obfuscation from Well-Founded Assumptions](https://mlsanity.com/paper/2008.09317/) (2020)
- [Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions](https://mlsanity.com/paper/2106.02619/) (2021)

## Built on by (most cited first, 6 of 6)

- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [Learning (Very) Simple Generative Models Is Hard](https://mlsanity.com/paper/2205.16003/) (2022)
- [Robust Estimation under the Wasserstein Distance](https://mlsanity.com/paper/2302.01237/) (2023)
- [Learning Polynomial Transformations](https://mlsanity.com/paper/2204.04209/) (2022)
- [Statistically Optimal Generative Modeling with Maximum Deviation from the Empirical Distribution](https://mlsanity.com/paper/2307.16422/) (2023)
- [Exploring Image Generation via Mutually Exclusive Probability Spaces and Local Correlation Hypothesis](https://mlsanity.com/paper/2506.21731/) (2025)

## Abstract (arXiv)

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.