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:Rd→Rd′, 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.