Learning (Very) Simple Generative Models Is Hard - Chen, Sitan; Li, Jerry; Li, Yuanzhi (2022 Neural Information Processing Systems, 2022)
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 .