A decade of algorithmic robust statistics

Music City Center 

The study of robust statistics was initiated by work of Anscombe, Tukey, and Huber in the 60s and 70s. Yet until recently, efficient algorithms for these questions eluded us in many important yet basic high-dimensional settings. However, around a decade ago, starting with the work of Diakonikolas et. al and Lai-Rao-Vempala, there was a bona fide revolution in the way we think about and design algorithms for dealing with high-dimensional outliers. Now, not only do we have polynomial time algorithms for many robust statistical tasks, we now even have practical algorithms, and we have also discovered deep connections between these tasks and other well-studied settings in statistics such as differential privacy, and learning with heavy tails. In this talk, I will survey some of the progress that has been made in this field, and then I will then discuss some exciting future directions, including connections to other aspects of statistics, learning theory, theoretical computer science, and perhaps unexpectedly, quantum computation.