# Being Robust (in High Dimensions) Can Be Practical

arXiv: https://arxiv.org/abs/1703.00893 · HTML: https://mlsanity.com/paper/1703.00893/

## Key facts

- Cited by 83 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2017.

## Built on by (most cited first, 30 of 83)

- [SPECTRE: Defending Against Backdoor Attacks Using Robust Statistics](https://mlsanity.com/paper/2104.11315/) (2021)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [DORO: Distributional and Outlier Robust Optimization](https://mlsanity.com/paper/2106.06142/) (2021)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [A Survey on Heterogeneous Federated Learning](https://mlsanity.com/paper/2210.04505/) (2022)
- [Statistical, Robustness, and Computational Guarantees for Sliced Wasserstein Distances](https://mlsanity.com/paper/2210.09160/) (2022)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [Knowledge Distillation for Federated Learning: a Practical Guide](https://mlsanity.com/paper/2211.04742/) (2022)
- [Robust Policy Gradient against Strong Data Corruption](https://mlsanity.com/paper/2102.05800/) (2021)
- [Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guarantees](https://mlsanity.com/paper/2205.11765/) (2022)
- [From Robustness to Privacy and Back](https://mlsanity.com/paper/2302.01855/) (2023)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [On the Privacy-Robustness-Utility Trilemma in Distributed Learning](https://mlsanity.com/paper/2302.04787/) (2023)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [A Survey of What to Share in Federated Learning: Perspectives on Model Utility, Privacy Leakage, and Communication Efficiency](https://mlsanity.com/paper/2307.10655/) (2023)
- [Corruption Robust Offline Reinforcement Learning with Human Feedback](https://mlsanity.com/paper/2402.06734/) (2024)
- [A Huber Loss Minimization Approach to Byzantine Robust Federated Learning](https://mlsanity.com/paper/2308.12581/) (2023)
- [Outlier-Robust Wasserstein DRO](https://mlsanity.com/paper/2311.05573/) (2023)
- [Robust Regression Revisited: Acceleration and Improved Estimation Rates](https://mlsanity.com/paper/2106.11938/) (2021)
- [Outlier-Robust Learning of Ising Models Under Dobrushin's Condition](https://mlsanity.com/paper/2102.02171/) (2021)
- [Outlier-Robust Sparse Estimation via Non-Convex Optimization](https://mlsanity.com/paper/2109.11515/) (2021)
- [Byzantine-Robust Online and Offline Distributed Reinforcement Learning](https://mlsanity.com/paper/2206.00165/) (2022)
- [Learning GMMs with Nearly Optimal Robustness Guarantees](https://mlsanity.com/paper/2104.09665/) (2021)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [List-Decodable Sparse Mean Estimation](https://mlsanity.com/paper/2205.14337/) (2022)

## Abstract (arXiv)

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.