The Complexity of Learning Generative Models

Generative models like diffusion models and GANs have exploded in popularity as powerful ways of modeling real-world data. Yet when it comes to provable guarantees, we know very little about why these frameworks are so effective or how to articulate what it is they are accomplishing. In this talk I'll describe some recent progress in this direction. In the first half, I'll give an efficient reduction from distribution learning to the supervised learning task of "score estimation." Notably, this reduction holds for essentially any distribution D, even highly non-log-concave ones. In contrast, previous works either incurred exponential dependence on parameters like dimension, or required strong distributional assumptions that preclude significant non-log-concavity of D. As neural networks are highly effective at score estimation in practice, our reduction provides strong justification for the empirical successes of diffusion models, the backbone of technologies like DALL-E 2. In the second half, I'll describe some negative results towards obtaining "end-to-end" guarantees for learning generative models. Suppose the learner even has access to samples from a distribution D which is a simple parametric transformation of pure Gaussian noise, namely via a two-layer ReLU network with logarithmically many neurons for every output coordinate. I'll show it is computationally hard to find any distribution which is statistically close to D, and briefly outline a route to sidestepping such hardness results using smoothed complexity.