Samuel Hopkins - Robust Mean Estimation in Nearly-Linear Time

From Katie Gentilello December 6th, 2019

17 plays 0 comments

Robust mean estimation is the following basic estimation question: given i.i.d. copies of a random vector X in d-dimensional Euclidean space of which a small constant fraction are corrupted, how well can you estimate the mean of the distribution? This is a classical problem in statistics, going back to the 60's and 70's, and has recently found application to many problems in reliable machine learning. However, in high dimensions, classical algorithms for this problem either were (1) computationally intractable, or (2) lost poly(d) factors in their accuracy guarantees. Recently, polynomial time algorithms have been demonstrated for this problem that still achieve (nearly) optimal error guarantees. However, the running times of these algorithms were either at least quadratic in dimension or in 1/(desired accuracy), running time overhead which renders them ineffective in practice. In this talk we give the first truly nearly linear time algorithm for robust mean estimation which achieves nearly optimal statistical performance. Our algorithm is based on the matrix multiplicative weights method. Based on joint work with Yihe Dong and Jerry Li, to appear in NeurIPS 2019.

Tags: arc colloquiumalgorithms and randomness centergeorgia techrecorded by gtlibraryfall 2019

name: Samuel Hopkins
Date: December 2nd, 2019
Appears In: Open Scholarship

Comments
Related Media

Loading…

Samuel Hopkins - Robust Mean Estimation in Nearly-Linear Time

Related Media