[Colloquium] REMINDER: 2/15 Talks at TTIC: Jerry Li, Microsoft Research

[Mary Marre via Colloquium]

When:     Friday, February 15th at *11:00 am*

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:      Jerry Li, Microsoft Research


*Title:*       Nearly optimal algorithms for robust mean estimation

*Abstract:* Robust mean estimation is the following basic estimation
question: given samples from a distribution, where an \epsilon-fraction of
them have been corrupted, how well can you estimate the mean of the
distribution? This is a classical problem in statistics, going back to the
60's and 70's, and has recently found application to many problems in
reliable machine learning. However, in high dimensions, classical
algorithms for this problem either were (1) computationally intractable, or
(2) lost poly(dimension) factors in their accuracy guarantees. Recently,
polynomial time algorithms have been demonstrated for this problem that
still achieve (nearly) optimal error guarantees. However, the runtimes of
these algorithms still had additional polynomial factors which can render
them ineffective in practice. In this talk we give the first truly nearly
linear time algorithms for these problems that achieve nearly optimal
statistical performance. The algorithms are surprisingly simple, and are
based on directly instantiating the matrix multiplicative weights
framework. Moreover, these algorithms apply very generally to a wide class
of distributions.

Joint work with Samuel B. Hopkins

Hosted by Sepideh Mahabadi  <mahabadi at ttic.edu>and Arturs Backurs
<backurs at ttic.edu>



Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*


On Mon, Feb 11, 2019 at 2:02 PM Mary Marre <mmarre at ttic.edu> wrote:

>
> When:     Friday, February 15th at *11:00 am*
>
> Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526
>
> Who:      Jerry Li, Microsoft Research
>
>
> *Title:*       Nearly optimal algorithms for robust mean estimation
>
> *Abstract:* Robust mean estimation is the following basic estimation
> question: given samples from a distribution, where an \epsilon-fraction of
> them have been corrupted, how well can you estimate the mean of the
> distribution? This is a classical problem in statistics, going back to the
> 60's and 70's, and has recently found application to many problems in
> reliable machine learning. However, in high dimensions, classical
> algorithms for this problem either were (1) computationally intractable, or
> (2) lost poly(dimension) factors in their accuracy guarantees. Recently,
> polynomial time algorithms have been demonstrated for this problem that
> still achieve (nearly) optimal error guarantees. However, the runtimes of
> these algorithms still had additional polynomial factors which can render
> them ineffective in practice. In this talk we give the first truly nearly
> linear time algorithms for these problems that achieve nearly optimal
> statistical performance. The algorithms are surprisingly simple, and are
> based on directly instantiating the matrix multiplicative weights
> framework. Moreover, these algorithms apply very generally to a wide class
> of distributions.
>
> Joint work with Samuel B. Hopkins
>
> Hosted by Sepideh Mahabadi <mahabadi at ttic.edu>and Arturs Backurs
> <backurs at ttic.edu>
>
>
>
>
>
> Mary C. Marre
> Administrative Assistant
> *Toyota Technological Institute*
> *6045 S. Kenwood Avenue*
> *Room 517*
> *Chicago, IL  60637*
> *p:(773) 834-1757*
> *f: (773) 357-6970*
>
> *mmarre at ttic.edu <mmarre at ttic.edu>*
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190214/918450a9/attachment-0001.html>