  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:\mathbb{R}^d\to\mathbb{R}^{d'}$, let
$D$ be the distribution over $\mathbb{R}^{d'}$ given by pushing the standard
Gaussian $\mathcal{N}(0,\textrm{Id}_d)$ 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
$\mathrm{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 $\mathcal{N}(0,1)$ under $f$ matches all
low-degree moments of $\mathcal{N}(0,1)$.
