@inproceedings{chen2022learning,
author = {Chen, Sitan and Li, Jerry and Li, Yuanzhi},
title = {Learning (Very) Simple Generative Models Is Hard},
booktitle = {2022 Neural Information Processing Systems},
year = {2022},
month = {May},
abstract = {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 , let  be the distribution over  given by pushing the standard Gaussian  through . Given i.i.d. samples from , the goal is to output  distribution close to  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  are one-hidden-layer ReLU networks with  neurons. Previously, the best lower bounds for this problem simply followed from lower bounds for   and required at least two hidden layers and  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  with polynomially-bounded slopes such that the pushforward of  under  matches all low-degree moments of .},
url = {http://approjects.co.za/?big=en-us/research/publication/learning-very-simple-generative-models-is-hard/},
}