mlsanityData to 14 Oct 2026

Learning (Very) Simple Generative Models Is Hard

arXiv 2205.16003 ↗First posted 31 May 2022cs.LG cs.CC cs.DScited by 9

Not on the map. Why?

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).

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

28 of 55 references.

References · 28

  1. 2015Variational Inference with Normalizing Flowscited by 2,170
  2. 2017Training GANs with Optimismcited by 217
  3. 2020A Review on Generative Adversarial Networks: Algorithms, Theory, and Applicationscited by 209
  4. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  5. 2018Adversarial examples from computational constraintscited by 80
  6. 2014On the Computational Efficiency of Training Neural Networkscited by 71
  7. 2018Negative Momentum for Improved Game Dynamicscited by 60
  8. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 58
  9. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  10. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  11. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  12. 2020Continuous LWEcited by 37
16 more
  1. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 28
  2. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  3. 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
  4. 2021From Local Pseudorandom Generators to Hardness of Learningcited by 24
  5. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  6. 2017On the Complexity of Learning Neural Networkscited by 18
  7. 2018Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Boundscited by 18
  8. 2019SGD Learns One-Layer Networks in WGANscited by 16
  9. 2020A Deep Conditioning Treatment of Neural Networkscited by 15
  10. 2020Hardness of Learning Neural Networks with Natural Weightscited by 15
  11. 2017Understanding GANs: the LQG Settingcited by 12
  12. 2019Learning Distributions Generated by One-Layer ReLU Networkscited by 10
  13. 2021Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributionscited by 9
  14. 2020The Sparse Hausdorff Moment Problem, with Application to Topic Modelscited by 6
  15. 2022Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANscited by 6
  16. 2022Learning Polynomial Transformationscited by 3

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 2; 2024: 5; 2025: 1.

9 papers.

  1. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptionscited by 445
  2. 2024On the Challenges and Opportunities in Generative AIcited by 31
  3. 2024Provably learning a multi-head attention layercited by 21
  4. 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
  5. 2023On the average-case complexity of learning output distributions of quantum circuitscited by 9
  6. 2024Statistical Query Lower Bounds for Learning Truncated Gaussianscited by 6
  7. 2024Sum-of-squares lower bounds for Non-Gaussian Component Analysiscited by 6
  8. 2025PTF Testing Lower Bounds for Non-Gaussian Component Analysiscited by 2
  9. 2023SQ Lower Bounds for Learning Bounded Covariance GMMscited by 0