mlsanityData to 14 Oct 2026

Agnostic Estimation of Mean and Covariance

arXiv 1604.06968 ↗First posted 24 Apr 2016cs.DS cs.LG stat.MLcited by 131

Not on the map. Why?

Abstract (arXiv)

We consider the problem of estimating the mean and covariance of a distribution from iid samples in ℝn, in the presence of an η fraction of malicious noise; this is in contrast to much recent work where the noise itself is assumed to be from a distribution of known type. The agnostic problem includes many interesting special cases, e.g., learning the parameters of a single Gaussian (or finding the best-fit Gaussian) when η fraction of data is adversarially corrupted, agnostically learning a mixture of Gaussians, agnostic ICA, etc. We present polynomial-time algorithms to estimate the mean and covariance with error guarantees in terms of information-theoretic lower bounds. As a corollary, we also obtain an agnostic algorithm for Singular Value Decomposition.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 35; 2022: 32; 2023: 21; 2024: 19; 2025: 15; 2026: 9.

131 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. 2021Robust and Differentially Private Mean Estimationcited by 66
  4. 2021Differential privacy and robust statistics in high dimensionscited by 64
  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. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  12. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
38 more
  1. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  2. 2021Byzantine-robust Federated Learning through Collaborative Malicious Gradient Filteringcited by 30
  3. 2022Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guaranteescited by 30
  4. 2022On the Impossible Safety of Large AI Modelscited by 28
  5. 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
  6. 2022Indiscriminate Data Poisoning Attacks on Neural Networkscited by 25
  7. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 24
  8. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  9. 2021Efficient Algorithms for Learning from Coarse Labelscited by 21
  10. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  11. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  12. 2024The Utility and Complexity of in- and out-of-Distribution Machine Unlearningcited by 20
  13. 2023Run-Off Election: Improved Provable Defense against Data Poisoning Attackscited by 17
  14. 2021Robust Regression Revisited: Acceleration and Improved Estimation Ratescited by 15
  15. 2024Tolerant Algorithms for Learning with Arbitrary Covariate Shiftcited by 15
  16. 2021Outlier-Robust Learning of Ising Models Under Dobrushin's Conditioncited by 14
  17. 2021Outlier-Robust Sparse Estimation via Non-Convex Optimizationcited by 14
  18. 2022On Optimal Learning Under Targeted Data Poisoningcited by 14
  19. 2021Learning and Certification under Instance-targeted Poisoningcited by 13
  20. 2022Byzantine-Robust Online and Offline Distributed Reinforcement Learningcited by 13
  21. 2022List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filteringcited by 13
  22. 2022Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributionscited by 13
  23. 2021Learning GMMs with Nearly Optimal Robustness Guaranteescited by 12
  24. 2021On the power of adaptivity in statistical adversariescited by 12
  25. 2022Minimax Rates for Robust Community Detectioncited by 12
  26. 2021Sample-Optimal PAC Learning of Halfspaces with Malicious Noisecited by 11
  27. 2022List-Decodable Sparse Mean Estimationcited by 11
  28. 2022Estimation Contracts for Outlier-Robust Geometric Perceptioncited by 11
  29. 2021ReLU Regression with Massart Noisecited by 10
  30. 2022Secure Federated Clusteringcited by 10
  31. 2023Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCAcited by 10
  32. 2024SoS Certifiability of Subgaussian Distributions and its Algorithmic Applicationscited by 10
  33. 2024Adaptive and oblivious statistical adversaries are equivalentcited by 9
  34. 2021Robust Estimation for Random Graphscited by 8
  35. 2022List-Decodable Covariance Estimationcited by 8
  36. 2021SoS Degree Reduction with Applications to Clustering and Robust Moment Estimationcited by 7
  37. 2022Reducing Certified Regression to Certified Classification for General Poisoning Attackscited by 7
  38. 2023High Dimensional Distributed Gradient Descent with Arbitrary Number of Byzantine Attackerscited by 7

50 most cited of 131 All 131 (JSON)