[Theory] NOW: 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>*


On Thu, Jan 27, 2022 at 10:32 AM Mary Marre <mmarre at ttic.edu> wrote:

> *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>*
>
>
> On Wed, Jan 26, 2022 at 1:28 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *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>*
>>
>>
>> On Thu, Jan 20, 2022 at 5:57 PM Mary Marre <mmarre at ttic.edu> wrote:
>>
>>> *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/20220127/6cc43aeb/attachment-0001.html>