Averaging data distributions is a core subroutine throughout data science. Wasserstein barycenters (a.k.a. Optimal Transport barycenters) provide a natural approach for this problem that captures the geometry of the data, and are central to diverse applications in machine learning, statistics, and computer graphics. However, despite considerable attention, it remained unknown whether Wasserstein barycenters can be computed in polynomial time. Our recent work provides a complete answer to this question and uncovers the subtle dependence of the answer on the dimension due to the continuous nature of the problem.

In this talk, Jason will explain these results and how they fit more broadly into the research program on algorithms for “structured” Multimarginal Optimal Transport problems.
Joint work with Enric Boix

Papers related to the talk:
https://arxiv.org/abs/2006.08012 (speaker will briefly mention how the following two papers connect to this direction: https://arxiv.org/abs/2101.01100 and https://arxiv.org/abs/2008.03006).

Jason Altschuler is a final-year PhD student in the Department of Electrical Engineering and Computer Science at MIT. Upon graduation, he will be a CDS Faculty Fellow at NYU Center for Data Science in 2022-2023, and then an assistant professor at the Wharton Department of Statistics and Data Science starting in 2023. His research interests are broadly at the intersection of optimization, probability, and machine learning, with a recent focus on computational aspects of problems related to optimal transport. His work is supported by the inaugural TwoSigma PhD fellowship and an NSF graduate fellowship.

For more information about the ESD Seminar, please email esd_invite@sutd.edu.sg