MFAI: Computational and Statistical Limits in Generative Sampling

This project aims to fill the gap in foundational knowledge between well-established sampling and estimation methods and Artificial Intelligence (AI)-inspired ones, referred to as ‘generative sampling.’ Generative AI algorithms are capable of producing plausible instances of objects from complex distributions, such as ‘naturally occurring’ sentences or ‘naturally occurring’ images. Rather than learning a probability distribution, these methods typically learn an ‘algorithm’ to generate samples with the desired distribution. This project has two main goals: (1) Determine the fundamental computational and statistical limitations of generative Artificial Intelligence (AI) methods, addressing what the classes of outputs (probability distributions) can and cannot be generated by these methods; (2) Design algorithms to accelerate the generation process. The project also involves training activities in this area through the involvement of undergraduate and graduate students in this research and the development of topics courses. More specifically, the project’s focus is on denoising diffusions, their generalization via stochastic localization, and related approaches. It appears that the scope and limitations of these methods are dictated by subtle properties of the target probability distribution. For instance, it can happen that a distribution can be sampled in polynomial time, and yet reasonable polynomial time generative processes, e.g., all denoising diffusions in a broad class, fail to sample correctly. The project aims to determine fundamental limitations both in terms of computational resources at generation time (computational bottlenecks) and the required sample size to estimate the denoiser (statistical bottlenecks), as well as optimal parallel generation algorithms when efficient generation is possible. 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.