Collaborative Research: AF: Small: Efficient Algorithms for Optimal Transport in Geometric Settings

Optimal transport (OT) is a powerful tool for comparing probability distributions and computing maps between them. Simply put, optimal transport is the minimum-cost plan to transport mass from one distribution to the other, where the cost of transporting one unit of mass between two locations is the ground distance between the two locations. OT has been studied extensively in mathematics, engineering, physics, economics, operations research, and computer science because of their numerous applications. Despite extensive work, computing OT plans has remained a computationally challenging problem, and there is a large gap between the theory and practice of OT algorithms. The need for fast OT algorithms is becoming even more urgent with the proliferation of machine learning and algorithmic decision making in all disciplines. The scarcity of scalable algorithms that compute high quality transport plans has limited the applicability OT to many applications. The main goal of this project is to advance the theoretical underpinnings of OT and to bridge the gap between the theory and practice of OT algorithms. By exploiting combinatorial, geometric and statistical properties of OT, leveraging new approaches for min-cost flow, and exploiting approximation and probabilistic techniques, simple and scalable algorithms will be developed for computing high quality OT plans of both discrete and continuous distributions whose supports are compact regions in Euclidean space. The emphasis will be on designing combinatorial algorithms that not only have good worst-case running time but that have better expected running time on stochastic or semi-stochastic inputs. The project will also explore techniques to circumvent the curse of dimensionality, which arises in the OT of high-dimensional distributions. Building on these OT algorithms, new algorithms will be developed for data analysis (e.g. clustering, training neural networks) on a family of distributions in Wasserstein space, i.e., using OT as the distance between a pair of distributions; for quality assessment of algorithms that return a probability distribution (e.g., flood-risk-analysis algorithms that return a distribution of water over a region). 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.