Computational Mathematics and Scientific Computing Seminar

---

High-precision computation of Wasserstein barycenters in low dimension: beyond gridding

Speaker: Jason Altschuler, Massachusetts Institute of Technology

Location: Online

Date: Oct. 15, 2021, 10 a.m.

Synopsis:

A major effort in modern data science is interpreting and extracting geometric information from data. In this talk, I’ll focus on my recent work on the core algorithmic task of averaging discrete data distributions. Wasserstein barycenters (aka Optimal Transport barycenters) provide a natural approach for this problem and are central to diverse applications in machine learning, statistics, and computer graphics. Despite considerable attention, even in dimension as low as 2, it remained unknown whether Wasserstein barycenters can be computed to high precision in polynomial time (i.e., with polylog(1/eps) runtime dependence rather than poly(1/eps)). We show that this is possible. Our algorithm solves an exponential-size linear program reformulation by efficiently implementing the corresponding separation oracle using techniques from computational geometry. This enables us to efficiently optimize over continuous space rather than just over grids, which is essential for obtaining high-precision solutions.

Joint work with Enric Boix-Adsera