Recent Advances in Algorithmic High-Dimensional Robust Statistics
This solves the fundamental problem of robust statistical estimation for researchers and practitioners dealing with high-dimensional data, but it is a survey article summarizing incremental progress rather than presenting new methods.
The paper addresses the problem of efficient unsupervised learning in high dimensions with outliers, where no efficient robust estimators existed previously, and recent advances have provided the first efficient algorithms for tasks like robust mean and covariance estimation.
Learning in the presence of outliers is a fundamental problem in statistics. Until recently, all known efficient unsupervised learning algorithms were very sensitive to outliers in high dimensions. In particular, even for the task of robust mean estimation under natural distributional assumptions, no efficient algorithm was known. Recent work in theoretical computer science gave the first efficient robust estimators for a number of fundamental statistical tasks, including mean and covariance estimation. Since then, there has been a flurry of research activity on algorithmic high-dimensional robust estimation in a range of settings. In this survey article, we introduce the core ideas and algorithmic techniques in the emerging area of algorithmic high-dimensional robust statistics with a focus on robust mean estimation. We also provide an overview of the approaches that have led to computationally efficient robust estimators for a range of broader statistical tasks and discuss new directions and opportunities for future work.