We study high-dimensional sparse estimation tasks in a robust setting where a
constant fraction of the dataset is adversarially corrupted. Specifically, we
focus on the fundamental problems of robust sparse mean estimation and robust
sparse PCA. We give the first practically viable robust estimators for these
problems. In more detail, our algorithms are sample and computationally
efficient and achieve near-optimal robustness guarantees. In contrast to prior
provable algorithms which relied on the ellipsoid method, our algorithms use
spectral techniques to iteratively remove outliers from the dataset. Our
experimental evaluation on synthetic data shows that our algorithms are
scalable and significantly outperform a range of previous approaches, nearly
matching the best error rate without corruptions.
Description
[1911.08085] Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering
%0 Journal Article
%1 diakonikolas2019outlierrobust
%A Diakonikolas, Ilias
%A Karmalkar, Sushrut
%A Kane, Daniel
%A Price, Eric
%A Stewart, Alistair
%D 2019
%K outliers robustness stats
%T Outlier-Robust High-Dimensional Sparse Estimation via Iterative
Filtering
%U http://arxiv.org/abs/1911.08085
%X We study high-dimensional sparse estimation tasks in a robust setting where a
constant fraction of the dataset is adversarially corrupted. Specifically, we
focus on the fundamental problems of robust sparse mean estimation and robust
sparse PCA. We give the first practically viable robust estimators for these
problems. In more detail, our algorithms are sample and computationally
efficient and achieve near-optimal robustness guarantees. In contrast to prior
provable algorithms which relied on the ellipsoid method, our algorithms use
spectral techniques to iteratively remove outliers from the dataset. Our
experimental evaluation on synthetic data shows that our algorithms are
scalable and significantly outperform a range of previous approaches, nearly
matching the best error rate without corruptions.
@article{diakonikolas2019outlierrobust,
abstract = {We study high-dimensional sparse estimation tasks in a robust setting where a
constant fraction of the dataset is adversarially corrupted. Specifically, we
focus on the fundamental problems of robust sparse mean estimation and robust
sparse PCA. We give the first practically viable robust estimators for these
problems. In more detail, our algorithms are sample and computationally
efficient and achieve near-optimal robustness guarantees. In contrast to prior
provable algorithms which relied on the ellipsoid method, our algorithms use
spectral techniques to iteratively remove outliers from the dataset. Our
experimental evaluation on synthetic data shows that our algorithms are
scalable and significantly outperform a range of previous approaches, nearly
matching the best error rate without corruptions.},
added-at = {2020-02-26T13:35:18.000+0100},
author = {Diakonikolas, Ilias and Karmalkar, Sushrut and Kane, Daniel and Price, Eric and Stewart, Alistair},
biburl = {https://www.bibsonomy.org/bibtex/2d41566324593dd3ad81cc6015cad9e9a/kirk86},
description = {[1911.08085] Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering},
interhash = {058874dc9cd2c220b6dedbd8fd619771},
intrahash = {d41566324593dd3ad81cc6015cad9e9a},
keywords = {outliers robustness stats},
note = {cite arxiv:1911.08085},
timestamp = {2020-02-26T13:35:18.000+0100},
title = {Outlier-Robust High-Dimensional Sparse Estimation via Iterative
Filtering},
url = {http://arxiv.org/abs/1911.08085},
year = 2019
}