The aim of this project is to develop scalable algorithms with provable guarantees for sampling from probability distributions. Sampling is a fundamental primitive that is deployed in a variety of summarization, inference, training, and simulation related tasks in several areas including machine learning, statistics, optimization, theoretical computer science, and molecular dynamics. The approach of this project would be to study certain widely deployed heuristics for sampling that have their roots in classical physics, but for whom a rigorous understanding of the conditions under which they work is lacking. This project will contribute to speeding up core tasks in emergent machine-learning-based technologies that rely on optimization and sampling, advance the technical core of computer science by infusing it with ideas from physics, and prepare a new generation of graduate and undergraduate students that are adept at these tasks.
An important example is the class of Hamiltonian Monte Carlo (HMC) Markov chain-based methods that possess the remarkable ability to take long steps in the domain and come with the promise of dimension-independent running times for sampling from regular-enough distributions. This ability of HMC to take long steps is derived from certain laws of physics - Hamiltonian dynamics - that underlie this method. This project expects to leverage this physics viewpoint to enable both the design of algorithms and their analysis by providing the right equations of motion, potential functions, a principled way of tuning parameters, and arriving at regularity conditions on the distribution. Making progress on the mathematical aspects of these physics-based methods requires a synthesis of algorithms, optimization, probability, geometry, dynamical systems, and intuition from physics. A key aspect of this project is to train the students involved in the relevant technical areas and inculcate a physics-based approach to thinking about algorithms in a wide audience.
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.
