2019/11/18 by Ilias Diakonikolas, Sushrut Karmalkar, Diakonikolas, Ilias +7
Computer Science · Engineering · Mathematics · #Advanced Statistical Methods and Models #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.1911.08085
openalex publication_date 2019/11/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study high-dimensional sparse estimation tasks in a robust setting where a\nconstant fraction of the dataset is adversarially corrupted. Specifically, we\nfocus on the fundamental problems of robust sparse mean estimation and robust\nsparse PCA. We give the first practically viable robust estimators for these\nproblems. In more detail, our algorithms are sample and computationally\nefficient and achieve near-optimal robustness guarantees. In contrast to prior\nprovable algorithms which relied on the ellipsoid method, our algorithms use\nspectral techniques to iteratively remove outliers from the dataset. Our\nexperimental evaluation on synthetic data shows that our algorithms are\nscalable and significantly outperform a range of previous approaches, nearly\nmatching the best error rate without corruptions.\n