Computing Wasserstein barycenters: easy or hard?

May 18, 2022 09:00 AM Singapore (Registration will open at 08:50 AM.)

Join Zoom Meeting:
https://sutd-edu.zoom.us/j/99973438000?pwd=NllSWlY5RjF2czhDQWlHTnVuMytEQT09

Meeting ID: 999 7343 8000
Passcode: HY5H2^8R

Abstract

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).

About the Speaker

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

Jason Altschuler (Massachusetts Institute of Technology) - Computing Wasserstein barycenters: easy or hard?