Speaker 1: Jason Altschuler, MIT
Title 1: Computing Wasserstein barycenters: easy or hard?
Abstract 1: 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. 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 reveals a surprising “curse of dimensionality”.
Joint work with Enric Boix-Adserà
Speaker 2: Jay Mardia, Stanford
Title 2: Statistical-computational phenomena through different computational lenses: robustness and discovery
Abstract 2: Our aim will be to look at stat-comp phenomena through a lens of computational efficiency different from "efficient = polynomial time algorithm". When doing so, two natural questions arise.
1. Are known stat-comp phenomena robust to such a change? Or do these phenomena and the thresholds associated with them change based on our lens?
2. Are there new stat-comp phenomena waiting to be discovered by putting on new computational lenses?
We will study these questions using the planted clique problem and its associated stat-comp phenomena as our toy model.