Efficient Algorithms for Optimal Transport in Geometric Settings

Abstract

The optimal transport (OT) problem can be described simply as transporting a collection of identical goods from a set of source locations to a set of target locations with as little cost as possible. Optimal transport can be viewed as lifting a metric over points to a metric over sets of points (or more generally probability distributions). Often times in practice, representing complex objects as sets of points in Euclidean space equipped with the underlying geometry captures important structural and spatial properties of the objects. Thus OT has been widely used in numerous applications. However, the known algorithms for computing an OT map are computationally expensive and often ignore the rich geometry of the space which the data lies in. In this thesis, we aim to contribute to computational optimal transport by designing simple, efficient algorithms for various OT problems under various settings which exploit the underlying geometry of the inputs.In the first part of this thesis, we design approximation algorithms for computing OT plans under models of increasing complexity of the input probability distributions: discrete, semi-discrete, and continuous domains. In the discrete setting, we show that a simple geometric greedy algorithm outperforms state-of-the-art numerical preconditioning for gradient descent style algorithms. In the semi-discrete setting, we describe two approximation algorithms: the first uses an adaptive sampling technique and runs discrete OT on the sample, while the second one extends primal-dual algorithms to the semi-discrete setting and has a much smaller dependency on the approximation factor. For the continuous setting, we extend the geometric greedy algorithm to compute approximate optimal transport plans between histograms over the plane in near-quadratic time, and show that this algorithm is near optimal in the worst case. We additionally develop OT algorithms that are robust to noise in the input.In the second part, we develop efficient algorithms for the Wasserstein barycenter problem, which asks to compute an average probability distribution over a collection of given distributions. We first design an exact algorithm for the Wasserstein barycenter problem in tree metrics in near-linear time. We then couple this algorithm with the multiplicative weights update (MWU) method to obtain a near-linear time approximation algorithm for the 1-Wasserstein barycenter problem in Euclidean space. We additionally design a different near-linear time, MWU-based approximation algorithm for the more general p-Wasserstein barycenter problem, which is inspired by an approximation algorithm for multi-commodity flows. We conclude this thesis by designing algorithms for the Wasserstein barycenter problem that are robust to noise.