Description and Outline

One of the major recent advances in theoretical machine learning is the development of efficient learning algorithms for various high-dimensional statistical models. The Achilles heel of these algorithms is the assumption that the samples are precisely generated from the model. This assumption is crucial for the performance of these algorithms: even a very small fraction of outliers can completely compromise the algorithms' behavior.

Recent results in theoretical computer science have led to the development of the first computationally efficient robust estimators for a range of high-dimensional models. The goal of this tutorial is to introduce the machine learning community to the core insights and techniques in this area of algorithmic robust statistics, and discuss new directions and opportunities for future work.

Slides

• Part 1: Introduction and Robust Mean Estimation [pdf] [video]


• Part 2: Basic Algorithmic Techniques [pdf] [video]


• Part 3: Experiments and Extensions [pdf] [video]


• Part 4: Computational-Statistical Tradeoffs and Research Directions [pdf] [video]

Main References

I. Diakonikolas, D. Kane. Recent Advances in Algorithmic High-Dimensional Robust Statistics. Invited Book Chapter in Beyond the Worst-Case Analysis of Algorithms, Cambridge University Press, September 2020.

I. Diakonikolas, G. Kamath, D. Kane, J. Li, A. Moitra and A. Stewart. Robust Estimators in High Dimensions without the Computational Intractability, FOCS 2016.

K. Lai, A. Rao and S. Vempala. Agnostic Estimation of Mean and Covariance, FOCS 2016.

I. Diakonikolas, G. Kamath, D. Kane, J. Li, A. Moitra and A. Stewart. Being Robust (in High Dimensions) Can Be Practical, ICML 2017.

I. Diakonikolas, D. Kane and A. Stewart. Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures, FOCS 2017.

I. Diakonikolas, G. Kamath, D. Kane, J. Li, A. Moitra and A. Stewart. Robustly Learning a Gaussian: Getting Optimal Error, Efficiently , SODA 2018.

I. Diakonikolas, G. Kamath, D. Kane, J. Li, J. Steinhardt, A. Stewart. Sever: A Robust Meta-Algorithm for Stochastic Optimization, ICML 2019.