Transport and Beyond: Efficient Optimization over Probability Distributions

Jason Altschuler – Massachusetts Institute of Technology

Abstract

The core of classical optimization focuses on the setting where decision variables are vectors in R^d. However, modern applications throughout machine learning, statistics, and engineering demand high-dimensional optimization problems where decision variables are probability distributions. Can such optimization problems be solved efficiently? This talk presents two vignettes in this direction.

The first vignette concerns entropic optimal transport and related problems including Min-Mean-Cycle and Matrix Preconditioning. We present approximation algorithms that are faster in both theory and practice, yielding near-linear runtimes in general, and even faster runtimes in commonly arising geometric settings. The second vignette concerns Wasserstein barycenters and more generally, multimarginal optimal transport problems. Despite considerable attention, even in dimension as low as 2, it remained unknown whether Wasserstein barycenters can be computed in polynomial time. We uncover the subtle dependence of the answer on the dimension: yes in fixed dimension and no in general. Taken together, these two vignettes illustrate the growing interface of optimization, probability, and efficient algorithms.

I will mostly focus on the following two papers but will mention how a few other papers connect to this direction:
https://arxiv.org/abs/1705.09634
https://arxiv.org/abs/2006.08012