Being Robust (in High Dimensions) Can Be Practical

Abstract

Robust estimation is much more challenging in high dimensions than it is in one dimension: Most techniques either lead to intractable optimization problems or estimators that can tolerate only a tiny fraction of errors. Recent work in theoretical computer science has shown that, in appropriate distributional models, it is possible to robustly estimate the mean and covariance with polynomial time algorithms that can tolerate a constant fraction of corruptions, independent of the dimension. However, the sample and time complexity of these algorithms is prohibitively large for high-dimensional applications. In this work, we address both of these issues by establishing sample complexity bounds that are optimal, up to logarithmic factors, as well as giving various refinements that allow the algorithms to tolerate a much larger fraction of corruptions. Finally, we show on both synthetic and real data that our algorithms have state-of-the-art performance and suddenly make high-dimensional robust estimation a realistic possibility.

Appeared in ICML 2017

References in corpus (2)

• Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians
• Robust Sparse Estimation Tasks in High Dimensions

Cited by in corpus (19)

• Robust Federated Learning in a Heterogeneous Environment
• Cronus: Robust and Heterogeneous Collaborative Learning with Black-Box Knowledge Transfer
• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• Generalized Resilience and Robust Statistics
• Robust Estimation and Generative Adversarial Nets
• Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
• Robust and Differentially Private Mean Estimation
• Outlier Robust Mean Estimation with Subgaussian Rates via Stability
• Robust Policy Gradient against Strong Data Corruption
• Learning Discrete Distributions from Untrusted Batches
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• DORO: Distributional and Outlier Robust Optimization
• Robust Meta-learning for Mixed Linear Regression with Small Batches
• Differential privacy and robust statistics in high dimensions
• Robust Inference Under Heteroskedasticity via the Hadamard Estimator
• Robust Estimation of Covariance Matrices: Adversarial Contamination and Beyond
• Designing Differentially Private Estimators in High Dimensions
• Efficient Statistics for Sparse Graphical Models from Truncated Samples
• Adversarial Robust Low Rank Matrix Estimation: Compressed Sensing and Matrix Completion