Timezone: »

 
Poster
Learning (Very) Simple Generative Models Is Hard
Sitan Chen · Jerry Li · Yuanzhi Li

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #828
in Poster Session 1 »
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 $\textrm{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)$.
Keywords: Generative Models · Computational hardness · distribution learning · computational-statistical tradeoffs · statistical query
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Sitan Chen (University of California Berkeley)
Jerry Li (Microsoft)
Yuanzhi Li (CMU)

More from the Same Authors