Learning (Very) Simple Generative Models Is Hard
Authors: Sitan Chen, Jerry Li, Yuanzhi Li
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 Re LU 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 [CGKM22, DV21]. 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). |
| Researcher Affiliation | Collaboration | Sitan Chen UC Berkeley sitanc@berkeley.edu Jerry Li Microsoft Research jerrl@microsoft.com Yuanzhi Li CMU yuanzhil@andrew.cmu.edu |
| Pseudocode | No | The paper contains mathematical proofs and definitions but no pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not mention releasing any source code. |
| Open Datasets | No | The paper is theoretical and does not use or mention any datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not discuss dataset splits for validation or training. |
| Hardware Specification | No | The paper is theoretical and does not mention any hardware specifications for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |