Description and Outline

Fitting a model to a collection of observations is one of the quintessential questions in statistics and machine learning. The typical assumption is that the data was generated by a model of a given type (e.g., a mixture model). This is a simplifying assumption that is only approximately valid, as real datasets are typically exposed to some source of contamination. Hence, any estimator designed for a particular model must also be robust in the presence of corrupted/noisy data. Classical work in robust statistics, starting with the pioneering works of Tukey and Huber in the 1960s, pinned down the fundamental information-theoretic aspects of high-dimensional robust estimation. In contrast, until very recently, the computational aspects have been poorly understood. In particular, even for the basic problem of robustly estimating the mean of a high-dimensional dataset, all known robust estimators were hard to compute. Moreover, the accuracy of the known heuristics (e.g., RANSAC) degrades polynomially as the dimension increases. This state of affairs prompted the following natural question:

Can we reconcile robustness and computational efficiency in high-dimensional estimation?

A recent line of work in theoretical computer science obtained the first computationally efficient robust estimators for a range of high-dimensional estimation tasks. In this tutorial talk, we will survey the algorithmic techniques underlying these estimators and the connections between them. We will illustrate these techniques for the following problems and settings: robust mean and covariance estimation, robust stochastic optimization, robust estimation under sparsity assumptions, list-decodable learning and mixture models, robust estimation of higher moments, computational-robustness tradeoffs. Finally, we will discuss new directions and opportunities for future work.

Schedule and Slides

Time	Talk
2:00 - 3:15	Ilias Diakonikolas Introduction; Robust Mean Estimation and Applications
3:30- 4:30	Daniel Kane Four Vignettes: Robust Covariance Estimation, List-Decodable Learning, Robust Estimation of High-Degree Moments, Robust Sparse Estimation
4:30- 5:00	Ilias Diakonikolas Computational-Statistical Tradeoffs and Open Problems

Related References

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.

S. Balakrishnan, S. S. Du, J. Li, A. Singh. Computationally Efficient Robust Sparse Estimation in High Dimensions, COLT 2017.

M. Charikar, J. Steinhardt, G. Valiant. Learning from Untrusted Data, STOC 2017.

I. Diakonikolas, D. M. Kane, A. Stewart. List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians, STOC 2018.

S. B. Hopkins, J. Li. Mixture Models, Robustness, and Sum of Squares Proofs, STOC 2018.

P. Kothari, J. Steinhardt, D. Steurer. Robust moment estimation and improved clustering via sum of squares, STOC 2018.

I. Diakonikolas, D. Kane, A. Stewart. Learning Geometric Concepts with Nasty Noise, STOC 2018.

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

A. Prasad, A. S. Suggala, S. Balakrishnan, P. Ravikumar. Robust Estimation via Robust Gradient Estimation, 2018.