CAREER: Pushing the Frontiers of Sampling and Inference

About This Grant

Probability distributions fruitfully model phenomena in all areas of science and engineering. In the modern age of large-scale computing and "big data", these distributions are incredibly complex and high-dimensional. Sampling is a universal algorithmic primitive used to manipulate and understand such probability distributions. The key challenge practitioners face is designing efficient algorithms which are guaranteed to generate random samples from the correct distribution. This is a fundamental computational task which lies at the heart of a vast array of real-world applications, including the recent revolution in generative artificial intelligence, the design of algorithms which simultaneously operate on user data while protecting user privacy, the study of materials in physics and chemistry, and statistical inference in science more broadly. The goal of this project will be to develop new mathematical tools to analyze sampling algorithms used ubiquitously in practice. The project will focus on a few foundational problems in theoretical computer science which have been open for decades. The insights derived from this research will be leveraged to design new algorithms which are not only fast in practice but also come with mathematically rigorous guarantees on the quality of their output. This research will be conducted in collaboration with a graduate student and integrated into educational materials at the undergraduate and graduate levels. Sampling is a universal algorithmic primitive for manipulating and understanding complex and high-dimensional probability distributions, with applications to materials science, statistical physics, Bayesian inference, differential privacy, fairness, generative artificial intelligence, and more. However, the fundamental challenge practitioners face is designing efficient algorithms which are guaranteed to generate random samples from the correct distribution. This project aims to develop robust mathematical techniques for analyzing Markov chains, which are algorithms ubiquitously used in practice for sampling, optimization, and inference tasks. We focus on three basic problems along the boundary between computationally tractable and intractable, each of which captures a specific barrier in the field: (1) Prove that local Markov chains like Glauber dynamics efficiently sample a uniformly random proper coloring of any graph with maximum degree d as long as q >= d+2. This 30-year-old open problem is central to understanding the worst-case complexity of sampling for general graphical models in statistical physics and machine learning. (2) Show that, in polynomial time, local Markov chains achieve optimal correlation with the ground truth in the stochastic block model of community detection. This is an important problem towards explaining the empirical efficacy of Markov chains in solving optimization and inference tasks despite failing to efficiently converge to stationarity. The insights from this direction will also provide a foothold for designing new inference algorithms which succeed when naive Markov chains fail. (3) Given that real-world instances are typically not worst-case, understanding when and how we can circumvent known NP-hardness barriers for sampling is an important endeavor. A representative average-case problem in this direction is to design an efficient algorithm which samples a uniformly random independent set in a random graph. 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.