CIS Theory Seminar Series: Ankur Moitra

3401 Walnut St, 401B

November 1, 2019

12:00 PM - 1:00 PM

Title: Robustness Meets Algorithms

Abstract: 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 high-dimensional 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.

This is based on joint work with Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li and Alistair Stewart. Time permitting, I will survey further developments in algorithmic robust statistics.

Bio: Ankur Moitra is an Associate Professor of Applied Mathematics at MIT’s Department of Mathematics and a Principal Investigator at MIT Computer Science and Artificial Intelligence Laboratory (CSAIL). The aim of his work is to bridge the gap between theoretical computer science and machine learning by developing algorithms with provable guarantees and foundations for reasoning about their behavior. Prior to that, he was an NSF Computing and Innovation Fellow at the Institute for Advanced Study (IAS), and also a senior postdoc in the Computer Science Department at Princeton University. He completed his PhD and MS at MIT in 2011 and 2009 respectively, where he was advised by Tom Leighton. In 2007 as an undergrad, Ankur received his BS in electrical and computer engineering from Cornell University. He is a recipient of a Packard Fellowship, a Sloan Fellowship, an NSF CAREER Award, an NSF Computing and Innovation Fellowship, and a Hertz Fellowship.