mlsanityData to 14 Oct 2026

Robust Estimators in High Dimensions without the Computational Intractability

arXiv 1604.06443 ↗First posted 21 Apr 2016cs.DS cs.IT cs.LGcited by 209

Not on the map. Why?

Abstract (arXiv)

We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an varepsilon-fraction of the samples. Such questions have a rich history spanning statistics, machine learning and theoretical computer science. Even in the most basic settings, the only known approaches are either computationally inefficient or lose dimension-dependent factors in their error guarantees. This raises the following question:Is high-dimensional agnostic distribution learning even possible, algorithmically? In this work, we obtain the first computationally efficient algorithms with dimension-independent error guarantees for agnostically learning several fundamental classes of high-dimensional distributions: (1) a single Gaussian, (2) a product distribution on the hypercube, (3) mixtures of two product distributions (under a natural balancedness condition), and (4) mixtures of spherical Gaussians. Our algorithms achieve error that is independent of the dimension, and in many cases scales nearly-linearly with the fraction of adversarially corrupted samples. Moreover, we develop a general recipe for detecting and correcting corruptions in high-dimensions, that may be applicable to many other problems.

Key facts. Cited by 209 papers in the map (data through 14 Oct 2026). First posted on arXiv 21 Apr 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 44; 2022: 45; 2023: 38; 2024: 31; 2025: 25; 2026: 26.

209 papers.

Sort:

By area:

  1. 2021Remember What You Want to Forget: Algorithms for Machine Unlearningcited by 371
  2. 2021SPECTRE: Defending Against Backdoor Attacks Using Robust Statisticscited by 130
  3. 2021Data Collection and Quality Challenges in Deep Learning: A Data-Centric AI Perspectivecited by 116
  4. 2021Robust and Differentially Private Mean Estimationcited by 66
  5. 2022Byzantine Machine Learning Made Easy by Resilient Averaging of Momentumscited by 63
  6. 2021Property Inference From Poisoningcited by 60
  7. 2021DORO: Distributional and Outlier Robust Optimizationcited by 56
  8. 2022Improved Certified Defenses against Data Poisoning with (Deterministic) Finite Aggregationcited by 52
  9. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  10. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  11. 2021Alternative Microfoundations for Strategic Classificationcited by 47
  12. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
38 more
  1. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  2. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  3. 2024LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformerscited by 37
  4. 2024How Does Unlabeled Data Provably Help Out-of-Distribution Detection?cited by 36
  5. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  6. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 33
  7. 2022Private Estimation with Public Datacited by 32
  8. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  9. 2022Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guaranteescited by 30
  10. 2023From Robustness to Privacy and Backcited by 27
  11. 2022COPA: Certifying Robust Policies for Offline Reinforcement Learning against Poisoning Attackscited by 26
  12. 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
  13. 2022Indiscriminate Data Poisoning Attacks on Neural Networkscited by 25
  14. 2022Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variancecited by 24
  15. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 24
  16. 2023On the Privacy-Robustness-Utility Trilemma in Distributed Learningcited by 24
  17. 2024Unraveling the Smoothness Properties of Diffusion Models: A Gaussian Mixture Perspectivecited by 24
  18. 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
  19. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  20. 2021Efficient Algorithms for Learning from Coarse Labelscited by 21
  21. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  22. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  23. 2021Robust Training in High Dimensions via Block Coordinate Geometric Median Descentcited by 20
  24. 2024The Utility and Complexity of in- and out-of-Distribution Machine Unlearningcited by 20
  25. 2021Fairness-Aware PAC Learning from Corrupted Datacited by 18
  26. 2022Holistic Robust Data-Driven Decisionscited by 18
  27. 2023Run-Off Election: Improved Provable Defense against Data Poisoning Attackscited by 17
  28. 2023A Huber Loss Minimization Approach to Byzantine Robust Federated Learningcited by 16
  29. 2021Robust Regression Revisited: Acceleration and Improved Estimation Ratescited by 15
  30. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  31. 2024Tolerant Algorithms for Learning with Arbitrary Covariate Shiftcited by 15
  32. 2021Outlier-Robust Learning of Ising Models Under Dobrushin's Conditioncited by 14
  33. 2021Outlier-Robust Sparse Estimation via Non-Convex Optimizationcited by 14
  34. 2022Learning from a Biased Samplecited by 14
  35. 2022On Optimal Learning Under Targeted Data Poisoningcited by 14
  36. 2021Learning and Certification under Instance-targeted Poisoningcited by 13
  37. 2022Byzantine-Robust Online and Offline Distributed Reinforcement Learningcited by 13
  38. 2022List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filteringcited by 13

50 most cited of 209 All 209 (JSON)