2022/05/31 by Sitan Chen, Chen, Sitan, Jerry Li +3 · 2 citations
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Neural Networks and Applications #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2205.16003
openalex publication_date 2022/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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:ℝd→ℝd', let D be the distribution over ℝd' given by pushing the standard Gaussian N(0,\textrmIdd) 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).