AISTATS 2021poster7 citations
Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers
Abstract
We study the problem of robustly estimating the mean of a $d$-dimensional distribution given $N$ examples, where most coordinates of every example may be missing and $\varepsilon N$ examples may be arbitrarily corrupted. Assuming each coordinate appears in a constant factor more than $\varepsilon N$ examples, we show algorithms that estimate the mean of the distribution with information-theoretically optimal dimension-independent error guarantees in nearly-linear time $\widetilde O(Nd)$. Our results extend recent work on computationally-efficient robust estimation to a more widely applicable incomplete-data setting.
BibTeX
@InProceedings{pmlr-v130-hu21b,
title = { Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers },
author = {Hu, Lunjia and Reingold, Omer},
booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics},
pages = {1558--1566},
year = {2021},
editor = {Banerjee, Arindam and Fukumizu, Kenji},
volume = {130},
series = {Proceedings of Machine Learning Research},
month = {13--15 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v130/hu21b/hu21b.pdf},
url = {https://proceedings.mlr.press/v130/hu21b.html},
abstract = { We study the problem of robustly estimating the mean of a $d$-dimensional distribution given $N$ examples, where most coordinates of every example may be missing and $\varepsilon N$ examples may be arbitrarily corrupted. Assuming each coordinate appears in a constant factor more than $\varepsilon N$ examples, we show algorithms that estimate the mean of the distribution with information-theoretically optimal dimension-independent error guarantees in nearly-linear time $\widetilde O(Nd)$. Our results extend recent work on computationally-efficient robust estimation to a more widely applicable incomplete-data setting. }
}