Learning (Very) Simple Generative Models Is Hard

Sitan Chen, Jerry Li, Yuanzhi Li

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:\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 $\mathrm{poly}(d)$ neurons. 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)$.

Introduction

Deep generative models, such as Generative Adversarial Networks (GANs) and Variational Autoencoders (VAEs), have demonstrated a remarkable ability to capture complex, high-dimensional data distributions. Despite their empirical success, a significant theoretical gap remains: why are these models so effectively learnable? This paper provides a sobering counterpoint to empirical optimism, demonstrating that even the simplest possible generative models—those consisting of a single hidden layer with a logarithmic number of neurons—are computationally "hard" to learn in the worst case.

The Problem: Learning Pushforward Distributions

At the heart of modern generative modeling is the concept of a pushforward distribution. A simple source distribution (typically a standard Gaussian $\mathcal{N}(0, I_d)$) is passed through a neural network $F$. The resulting distribution $D$ can be incredibly complex. The fundamental question addressed here is: When is it computationally feasible to learn $D$ from samples?

Prior research established that learning these distributions is difficult when the generator $F$ is deep (two or more hidden layers) and contains a large number of neurons. However, this left open the possibility that very shallow or small networks might be efficiently learnable. This work closes that gap by proving that even a one-hidden-layer ReLU network with only $O(\log d)$ neurons can generate a distribution that is computationally indistinguishable from pure noise.

Methodology: The Statistical Query Model

To establish these hardness results, the authors utilize the Statistical Query (SQ) model. The SQ framework is a standard tool in computational learning theory that encompasses a vast majority of algorithmic techniques used in modern machine learning, including gradient descent, expectation-maximization, and various method-of-moments approaches.

In the SQ model, an algorithm does not have direct access to samples. Instead, it can only request the expected value of any bounded function over the distribution. Proving hardness in the SQ model is a strong indicator that no efficient general-purpose algorithm can solve the problem.

Technical Innovation: The ODE-Based Construction

The core challenge in proving hardness is constructing a "hard instance": a simple neural network $f$ whose output distribution looks like a standard Gaussian to any efficient algorithm, despite being statistically distinct. The authors achieve this through a novel Ordinary Differential Equation (ODE)-based construction:

  1. Moment Matching: They begin with a discontinuous step function that matches the low-degree statistical moments (mean, variance, etc.) of a Gaussian. If the first $k$ moments match, an algorithm requires a massive number of queries to detect a difference.
  2. Continuous Evolution: Since step functions are not neural networks, the authors use an ODE to "evolve" this function into a continuous, piecewise-linear ReLU network.
  3. Weight Constraints: This evolution is carefully controlled to ensure the resulting network has "polynomially bounded weights." This ensures the network is a realistic, simple model rather than a mathematical artifact with extreme slopes that would be easy to detect.

Key Results

1. The Hardness Theorem

The paper proves that for any dimension $d$, there exists a family of one-hidden-layer ReLU networks with only $O(\log d / \log \log d)$ neurons such that any SQ algorithm requires super-polynomial time to distinguish the model's output from a standard Gaussian. This is a significant improvement over previous bounds that required much larger and deeper architectures.

2. Computational vs. Statistical Distance

A critical insight of this work is the gap between statistical and computational distance. While the "hard" distribution and the Gaussian are statistically very far apart (meaning they could be distinguished with infinite computing power), they are computationally indistinguishable. No practical algorithm can tell them apart in a reasonable timeframe.

3. Robustness to Improper Learning

The result is not limited to "proper" learning (where the learner tries to find the exact weights of the network). It applies to improper learning as well: it is computationally hard to output any distribution that is even moderately close to the target distribution in statistical distance.

Discussion and Implications

This research suggests that the simplicity of a network architecture does not guarantee ease of learning. If even a single-layer network with a handful of neurons can create a "computational brick wall," why do GANs and VAEs work so well on real-world data?

The authors suggest that the success of generative models must stem from the specific structure of real-world data—such as the manifold hypothesis—rather than the inherent properties of the networks themselves. While the worst-case scenarios constructed in this paper are hard, real-world data may lack the "computational camouflage" found in these synthetic instances.

Future work may focus on smoothed analysis, investigating whether the addition of small random noise to the network weights makes these hard instances disappear. Such a finding would help bridge the gap between this theoretical hardness and the practical success of deep learning.

Summary updated

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:\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 $\mathrm{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)$.
BibTeX
@inproceedings{chen2022learning,
  author = {Sitan Chen and Jerry Li and Yuanzhi Li},
  title = {{Learning (Very) Simple Generative Models Is Hard}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=UnygcA2BVzW},
}
Figure