Abstract

In recent years there has been significant interest in the theoretical foundations of diffusion generative modeling. One representative result in this line of work is that with an accurate estimate of the score function for the data distribution, one can approximately sample from virtually any bounded distribution in polynomial time. In this talk I will describe recent work on the missing piece left open by these works: when can we actually learn an accurate estimate of the score from data? I will focus on two vignettes: (1) learning Gaussian mixture models (GMMs), and (2) learning optimal estimators for compressed sensing.For (1), I will present an algorithm for score estimation based on piecewise polynomial regression, yielding the first quasipolynomial-time algorithm for learning general mixtures of Gaussians with polylogarithmically many components. For (2), I will give the first rigorous learning guarantee for algorithm unrolling, proving that a certain unrolled network, when trained on compressed sensing examples, learns to compete with Bayes approximate message passing.Based on joint works with Aayush Karan, Vasilis Kontonis, and Kulin Shah.