Graduate Text in Algorithmic Aspects of Robust Statistics

by Ilias Diakonikolas and Daniel M. Kane

Abstract:

The field of Robust Statistics studies the general problem of designing estimators that perform well even when the data significantly deviates from the idealized modeling assumptions. The systematic study of robust statistical procedures dates back to the pioneering works by Tukey and Huber in the 1960s. The classical statistical theory characterizes the information-theoretic limits of robust estimation for most common problems. On the other hand, until fairly recently, the computational aspects of this field were poorly understood. A recent line of work in computer science gave the first computationally efficient robust estimators in high dimensions for a range of learning tasks. Specifically, two independent and concurrent works in 2016 developed the first efficient algorithms for basic high-dimensional robust statistics tasks, including mean and covariance estimation. Since the dissemination of these works, there has been a flurry of research activity on algorithmic high-dimensional robust estimation in a variety of settings. This book provides an overview of the recent developments in algorithmic high-dimensional robust statistics.

Description:

This text is a free online version of a book to be published by Cambridge University Press.