CAREER: An Algorithmic Theory of Diffusion Models

This project seeks to forge new connections between the theory of distribution learning and the study of diffusion models, one of the primary arms of the recent revolution in generative artificial intelligence (AI). We seek to develop a rigorous mathematical framework that can shed light on the remarkable effectiveness of these models in capturing complex, high-dimensional distributions. Our work will advance the frontiers of machine learning theory by enriching the field with new definitions for what these models are accomplishing and new algorithmic goals more closely aligned with how they are used in practice. We aim to provide a theoretical foundation that can guide the development of more efficient and controllable generative models and reshape our understanding of what makes learning tractable in high dimensions. As this effort inherently straddles research divides across theory and practice, we will complement our mathematical insights with extensive experiments on real-world data and with the development of new educational materials and research opportunities at the undergraduate and graduate levels to expand participation in this rapidly growing field. This program is built around three thrusts. The first is to develop novel analytic tools to understand what makes score estimation, the key subroutine on which diffusion models are built, possible for real-world data distributions. We will explore how to leverage properties like low-dimensional manifold structure and stability under perturbation to prove end-to-end algorithmic guarantees for score estimation. Our second thrust introduces a new paradigm of learning: instead of trying to generate samples that are statistically close to the ground truth, we aim to develop learners that can generate samples which are computationally indistinguishable. We will explore whether diffusion models based on "computationally optimal score estimation" can achieve this goal. This new framework promises to better align theoretical guarantees with practice, potentially explaining the empirical success of diffusion models on distributions that were previously considered intractable to learn. Finally, our third thrust will develop a unified theory for solving downstream tasks via foundation models, like sampling acceleration, model distillation, and guided generation. The algorithms we develop here will suggest new design principles for practitioners that could lead to faster and more versatile generative modeling. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.