# Learning (Very) Simple Generative Models Is Hard

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 55 references that are in the map.
- First posted on arXiv 31 May 2022.

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

- [Variational Inference with Normalizing Flows](https://mlsanity.com/paper/1505.05770/) (2015)
- [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)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [On the Computational Efficiency of Training Neural Networks](https://mlsanity.com/paper/1410.1141/) (2014)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [Statistical-Query Lower Bounds via Functional Gradients](https://mlsanity.com/paper/2006.15812/) (2020)
- [Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2006.12476/) (2020)
- [Continuous LWE](https://mlsanity.com/paper/2005.09595/) (2020)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [Learning Deep ReLU Networks Is Fixed-Parameter Tractable](https://mlsanity.com/paper/2009.13512/) (2020)
- [Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures](https://mlsanity.com/paper/2204.02550/) (2022)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021)
- [On the Complexity of Learning Neural Networks](https://mlsanity.com/paper/1707.04615/) (2017)
- [Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds](https://mlsanity.com/paper/1805.02677/) (2018)
- [SGD Learns One-Layer Networks in WGANs](https://mlsanity.com/paper/1910.07030/) (2019)
- [A Deep Conditioning Treatment of Neural Networks](https://mlsanity.com/paper/2002.01523/) (2020)
- [Hardness of Learning Neural Networks with Natural Weights](https://mlsanity.com/paper/2006.03177/) (2020)
- [Understanding GANs: the LQG Setting](https://mlsanity.com/paper/1710.10793/) (2017)
- [Learning Distributions Generated by One-Layer ReLU Networks](https://mlsanity.com/paper/1909.01812/) (2019)
- [Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions](https://mlsanity.com/paper/2106.02619/) (2021)
- [The Sparse Hausdorff Moment Problem, with Application to Topic Models](https://mlsanity.com/paper/2007.08101/) (2020)
- [Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs](https://mlsanity.com/paper/2201.07206/) (2022)
- [Learning Polynomial Transformations](https://mlsanity.com/paper/2204.04209/) (2022)

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

- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [On the Challenges and Opportunities in Generative AI](https://mlsanity.com/paper/2403.00025/) (2024)
- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions](https://mlsanity.com/paper/2403.04744/) (2024)
- [On the average-case complexity of learning output distributions of quantum circuits](https://mlsanity.com/paper/2305.05765/) (2023)
- [Statistical Query Lower Bounds for Learning Truncated Gaussians](https://mlsanity.com/paper/2403.02300/) (2024)
- [Sum-of-squares lower bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2410.21426/) (2024)
- [PTF Testing Lower Bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2511.19398/) (2025)
- [SQ Lower Bounds for Learning Bounded Covariance GMMs](https://mlsanity.com/paper/2306.13057/) (2023)

## Abstract (arXiv)

Motivated by the recent empirical successes of deep generative models, we study the computational complexity of the following unsupervised learning problem. For an unknown neural network F:ℝd→ℝd', let D be the distribution over ℝd' given by pushing the standard Gaussian N(0,textrmIdd) through F. Given i.i.d. samples from D, the goal is to output any distribution close to D in statistical distance. We show under the statistical query (SQ) model that no polynomial-time algorithm can solve this problem even when the output coordinates of F are one-hidden-layer ReLU networks with log(d) neurons. Previously, the best lower bounds for this problem simply followed from lower bounds for supervised learning and required at least two hidden layers and poly(d) neurons [Daniely-Vardi '21, Chen-Gollakota-Klivans-Meka '22]. The key ingredient in our proof is an ODE-based construction of a compactly supported, piecewise-linear function f with polynomially-bounded slopes such that the pushforward of N(0,1) under f matches all low-degree moments of N(0,1).