Versatile and Scalable Sampling via Geometric Methods, Optimization, and Numerical Analysis

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

This project considers a core computational problem, namely, how to draw samples from a high-dimensional probability distribution. Being a fundamental task in science and engineering, the sampling problem involves generating representative examples of a stochastic object, and the ability to do so enables the modeling, simulation, and inference that are essential for understanding complex systems with uncertainties. Because of its importance, sampling is a classical problem that has been considered in statistics, physical sciences, and social sciences for decades. Moreover, it recently received renewed interest due to the exploding number of applications in data sciences, machine learning, and artificial intelligence, which motivates the research. The project aims to provide a better understanding of the existing practice and guide the construction of new methods that scale better. To address such an urgent need, this project will develop innovative and versatile sampling algorithms, together with analytical tools that can facilitate their design and certify their performance. More precisely, the intellectual merit of this project is to propose, in a principled and mathematically provable way, samplers that scale well (with dimension, condition number, etc.) and work in versatile setups (e.g., sampling from Euclidean space, sampling from a constrained domain, and sampling difficult multimodal distribution). This goal will be enabled via a synergy of three strategies. The first is to view a class of sampling algorithms as appropriate time discretizations of certain underlying dynamics in continuous time. This perspective allows the algorithmic design and analysis to be modularized into those for the continuous dynamics and those for the discretization, thus not only enabling an exploitation of profound mathematical tools but also helping better identify and focus on the true performance bottleneck. The second strategy is to leverage rich tools in optimization and extrapolate them to the sampling setup. It also includes a modern perspective, which is to view sampling as optimization in the infinite-dimensional space of probability distributions. The third strategy is to utilize geometric ideas, which not only lead to a deeper understanding of various sampling dynamics but also facilitate sampling from constrained distributions. Educational activities will be closely integrated with the research. 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.