Robustness Meets Algorithms

Starting from the seminal works of Tukey (1960) and Huber (1964), the field of robust statistics asks: Are there estimators that probably work in the presence of noise? The trouble is that all known provably robust estimators are also hard to compute in high-dimensions.

Here, we study a fundamental problem in robust statistics, posed in various forms in the above works. Given corrupted samples from a high-dimensional Gaussian, are there efficient algorithms to accurately estimate its parameters? We give the first algorithm that is able to tolerate a constant fraction of corruptions that is independent of the dimension. Moreover, we give a general recipe for detecting and correcting corruptions based on tensor-spectral techniques that are applicable to many other problems.

I will also discuss how this work fits into the broader agenda of developing mathematical and algorithmic foundations for modern machine learning.

Registration is required to receive the Zoom information

Register here to attend