Faster Algorithms for Optimal Transport

Carson Kent, Stanford University

Photo of Carson Kent

A classical problem in probability and statistics is that of finding an optimal coupling between two given probability distributions. In particular, given a function that quantifies the cost associated with a specific coupling, one can intuitively describe this problem as finding the least expensive way to transport mass from one probability distribution to another. This gives rise to the name "optimal transport." Many discrete and continuous problems arise as special cases of optimal transport, including multi-commodity flows, market clearing and congestion problems. More interestingly, however, optimal transport has given rise to a family of methods for performing distributionally robust optimization under Wasserstein metrics. In this work, we will review these existing methods for solving such problems arising from optimal transport and then provide a substantially faster algorithm, in theory and practice.

Abstract Author(s): Carson Kent, Jose Blanchet