mlsanityData to 7 Oct 2026

Recent Advances in Algorithmic High-Dimensional Robust Statistics

arXiv 1911.05911 ↗First posted 14 Nov 2019cs.DS cs.CC math.STcited by 100

Not on the map. Why?

Abstract (arXiv)

Learning in the presence of outliers is a fundamental problem in statistics. Until recently, all known efficient unsupervised learning algorithms were very sensitive to outliers in high dimensions. In particular, even for the task of robust mean estimation under natural distributional assumptions, no efficient algorithm was known. Recent work in theoretical computer science gave the first efficient robust estimators for a number of fundamental statistical tasks, including mean and covariance estimation. Since then, there has been a flurry of research activity on algorithmic high-dimensional robust estimation in a range of settings. In this survey article, we introduce the core ideas and algorithmic techniques in the emerging area of algorithmic high-dimensional robust statistics with a focus on robust mean estimation. We also provide an overview of the approaches that have led to computationally efficient robust estimators for a range of broader statistical tasks and discuss new directions and opportunities for future work.

Key facts. Cited by 100 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 Nov 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 28; 2022: 24; 2023: 26; 2024: 15; 2025: 4; 2026: 3.

100 papers.

Sort:

By area:

  1. 2022Is Out-of-Distribution Detection Learnable?cited by 109
  2. 2021Sample Selection with Uncertainty of Losses for Learning with Noisy Labelscited by 79
  3. 2021Robust and Differentially Private Mean Estimationcited by 66
  4. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  5. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  6. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  7. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  8. 2024How Does Unlabeled Data Provably Help Out-of-Distribution Detection?cited by 36
  9. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  10. 2021Clustering Mixtures with Almost Optimal Separation in Polynomial Timecited by 28
  11. 2022On the Impossible Safety of Large AI Modelscited by 27
  12. 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
38 more
  1. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  2. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 23
  3. 2022A Characterization of List Learnabilitycited by 22
  4. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  5. 2021Certifying Robustness to Programmable Data Bias in Decision Treescited by 21
  6. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  7. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  8. 2021Robust Training in High Dimensions via Block Coordinate Geometric Median Descentcited by 20
  9. 2023Backdoor Attacks Against Dataset Distillationcited by 20
  10. 2024Corruption Robust Offline Reinforcement Learning with Human Feedbackcited by 20
  11. 2021Distribution-Free Robust Linear Regressioncited by 19
  12. 2022Holistic Robust Data-Driven Decisionscited by 17
  13. 2023The Dataset Multiplicity Problem: How Unreliable Data Impacts Predictionscited by 17
  14. 2023Outlier-Robust Wasserstein DROcited by 16
  15. 2021Robust Regression Revisited: Acceleration and Improved Estimation Ratescited by 15
  16. 2024Tolerant Algorithms for Learning with Arbitrary Covariate Shiftcited by 15
  17. 2021Outlier-Robust Learning of Ising Models Under Dobrushin's Conditioncited by 14
  18. 2021Outlier-Robust Sparse Estimation via Non-Convex Optimizationcited by 14
  19. 2022On Optimal Learning Under Targeted Data Poisoningcited by 14
  20. 2021Learning and Certification under Instance-targeted Poisoningcited by 13
  21. 2022Byzantine-Robust Online and Offline Distributed Reinforcement Learningcited by 13
  22. 2022List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filteringcited by 13
  23. 2022Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributionscited by 13
  24. 2021Learning GMMs with Nearly Optimal Robustness Guaranteescited by 12
  25. 2021On the power of adaptivity in statistical adversariescited by 12
  26. 2021Sample-Optimal PAC Learning of Halfspaces with Malicious Noisecited by 11
  27. 2023Robust Nonparametric Regression under Poisoning Attackcited by 11
  28. 2021ReLU Regression with Massart Noisecited by 10
  29. 2023Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCAcited by 10
  30. 2021SoK: Machine Learning Governancecited by 9
  31. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  32. 2021Robust Estimation for Random Graphscited by 8
  33. 2023Robust Estimation under the Wasserstein Distancecited by 8
  34. 2023Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regressioncited by 7
  35. 2024Robust Kernel Hypothesis Testing under Data Corruptioncited by 7
  36. 2024Understanding In-Context Learning of Linear Models in Transformers Through an Adversarial Lenscited by 7
  37. 2021Mean-based Best Arm Identification in Stochastic Bandits under Reward Contaminationcited by 6
  38. 2022Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Modelscited by 6

50 most cited of 100 All 100 (JSON)