Robustness Meets Algorithms
COM1 Level 2
SR1, COM1-02-06
This is a distinguished talk as part of the NUS Computer Science Research Week 2019 (http://researchweek.comp.nus.edu.sg).
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.
The talk starts with a tutorial on the preliminaries and the theoretical foundations of this topic.
Biodata:
Ankur Moitra is the Rockwell International Associate Professor in the Department of Mathematics at MIT. He is a principal investigator in the Computer Science and Artificial Intelligence Lab (CSAIL), a core member of the Theory of Computation Group, Machine Learning@MIT and the Center for Statistics. 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. 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.