Processing math: 100%
Skip to yearly menu bar Skip to main content


Poster

Learning (Very) Simple Generative Models Is Hard

Sitan Chen · Jerry Li · Yuanzhi Li

Hall J (level 1) #828

Keywords: [ Generative Models ] [ distribution learning ] [ computational-statistical tradeoffs ] [ statistical query ] [ Computational hardness ]


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 F:RdRd, let D be the distribution over Rd given by pushing the standard Gaussian N(0,Idd) 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).

Chat is not available.