Statistics Seminar presents "Robustness meets algorithms"

Topic: 
"Robustness meets algorithms"
Tuesday, October 22, 2019 - 4:30pm
Venue: 
McCullough Building Room 115
Speaker: 
Ankur Moitra (MIT)
Abstract / Description: 

In every corner of machine learning and statistics, there is a need for estimators that work not just in an idealized model but even when their assumptions are violated. Unfortunately, in high-dimensions, being provably robust and efficiently computable are often at odds with each other.

In this talk, we give the first efficient algorithm for estimating the parameters of a highdimensional Gaussian which is able to tolerate a constant fraction of corruptions that is independent of the dimension. Prior to our work, all known estimators either needed time exponential in the dimension to compute, or could tolerate only an inverse polynomial fraction of corruptions. Not only does our algorithm bridge the gap between robustness and algorithms, it turns out to be highly practical in a variety of settings.