[Theory] 1/27 Talks at TTIC: Jason Altschuler, MIT

[Mary Marre]

*When:*      Thursday, January 27th at* 11:00 am CT*



*Where:*     Zoom Virtual Talk (*register in advance here
<https://uchicagogroup.zoom.us/webinar/register/WN_icenSqi8T-yFoYN942KgjA>*)


*Who: *       Jason Altschuler, MIT


*Title:        *Transport and Beyond: Efficient Optimization Over
Probability Distributions

*Abstract:*
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 dimension 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.

*Host:* *Nathan Srebro <nati at ttic.edu>*




Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Chicago, IL  60637*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220120/69eb370c/attachment-0001.html>