ORIE Special Seminar: Jason Altschuler (MIT)


Zoom Link - https://cornell.zoom.us/j/98920702306?pwd=Wjk4dmdCQlE1NVQvUTM3T1ptRzRCUT09


Transport and beyond: efficient optimization over probability distributions

The core of classical optimization focuses on the setting where decision variables are vectors in R^d. However, modern applications throughout machine learning, data science, 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 dimensions 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.

Jason Altschuler is a final-year Ph.D. student in the Department of Electrical Engineering and Computer Science at MIT, advised by Pablo Parrilo. 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 Ph.D. fellowship and an NSF graduate fellowship.