mlsanityData to 7 Oct 2026

Being Robust (in High Dimensions) Can Be Practical

arXiv 1703.00893 ↗First posted 2 Mar 2017cs.LG cs.DS cs.ITcited by 83

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 21; 2022: 21; 2023: 18; 2024: 14; 2025: 7; 2026: 2.

83 papers.

Sort:

By area:

  1. 2021SPECTRE: Defending Against Backdoor Attacks Using Robust Statisticscited by 123
  2. 2021Robust and Differentially Private Mean Estimationcited by 66
  3. 2021Differential privacy and robust statistics in high dimensionscited by 64
  4. 2021DORO: Distributional and Outlier Robust Optimizationcited by 54
  5. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  6. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  7. 2022A Survey on Heterogeneous Federated Learningcited by 42
  8. 2022Statistical, Robustness, and Computational Guarantees for Sliced Wasserstein Distancescited by 41
  9. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  10. 2022Knowledge Distillation for Federated Learning: a Practical Guidecited by 31
  11. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  12. 2022Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guaranteescited by 30
38 more
  1. 2023From Robustness to Privacy and Backcited by 27
  2. 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
  3. 2023On the Privacy-Robustness-Utility Trilemma in Distributed Learningcited by 24
  4. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 23
  5. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  6. 2021Efficient Algorithms for Learning from Coarse Labelscited by 21
  7. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  8. 2023A Survey of What to Share in Federated Learning: Perspectives on Model Utility, Privacy Leakage, and Communication Efficiencycited by 21
  9. 2024Corruption Robust Offline Reinforcement Learning with Human Feedbackcited by 20
  10. 2023A Huber Loss Minimization Approach to Byzantine Robust Federated Learningcited by 16
  11. 2023Outlier-Robust Wasserstein DROcited by 16
  12. 2021Robust Regression Revisited: Acceleration and Improved Estimation Ratescited by 15
  13. 2021Outlier-Robust Learning of Ising Models Under Dobrushin's Conditioncited by 14
  14. 2021Outlier-Robust Sparse Estimation via Non-Convex Optimizationcited by 14
  15. 2022Byzantine-Robust Online and Offline Distributed Reinforcement Learningcited by 13
  16. 2021Learning GMMs with Nearly Optimal Robustness Guaranteescited by 12
  17. 2022Minimax Rates for Robust Community Detectioncited by 12
  18. 2022List-Decodable Sparse Mean Estimationcited by 11
  19. 2023Robust Nonparametric Regression under Poisoning Attackcited by 11
  20. 2024A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacycited by 11
  21. 2021Heavy-tailed Streaming Statistical Estimationcited by 10
  22. 2023Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCAcited by 10
  23. 2024SoS Certifiability of Subgaussian Distributions and its Algorithmic Applicationscited by 10
  24. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  25. 2021Robust Estimation for Random Graphscited by 8
  26. 2025Towards Trustworthy Federated Learning with Untrusted Participantscited by 8
  27. 2023High Dimensional Distributed Gradient Descent with Arbitrary Number of Byzantine Attackerscited by 7
  28. 2023Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regressioncited by 7
  29. 2021Kalman Filtering with Adversarial Corruptionscited by 6
  30. 2022Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariatescited by 6
  31. 2024Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussianscited by 6
  32. 2022Towards a Defense Against Federated Backdoor Attacks Under Continuous Trainingcited by 5
  33. 2022Efficient List-Decodable Regression using Batchescited by 5
  34. 2024On the Byzantine-Resilience of Distillation-Based Federated Learningcited by 5
  35. 2024Robust Distribution Learning with Local and Global Adversarial Corruptionscited by 5
  36. 2025Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contaminationcited by 5
  37. 2022Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanismscited by 4
  38. 2022Robust estimation algorithms don't need to know the corruption levelcited by 4

50 most cited of 83 All 83 (JSON)