mlsanityData to 7 Oct 2026

Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization

arXiv 2007.15839 ↗First posted 31 Jul 2020cs.DS cs.LG math.STcited by 44

Not on the map. Why?

Abstract (arXiv)

We study the problem of estimating the mean of a distribution in high dimensions when either the samples are adversarially corrupted or the distribution is heavy-tailed. Recent developments in robust statistics have established efficient and (near) optimal procedures for both settings. However, the algorithms developed on each side tend to be sophisticated and do not directly transfer to the other, with many of them having ad-hoc or complicated analyses. In this paper, we provide a meta-problem and a duality theorem that lead to a new unified view on robust and heavy-tailed mean estimation in high dimensions. We show that the meta-problem can be solved either by a variant of the Filter algorithm from the recent literature on robust estimation or by the quantum entropy scoring scheme (QUE), due to Dong, Hopkins and Li (NeurIPS '19). By leveraging our duality theorem, these results translate into simple and efficient algorithms for both robust and heavy-tailed settings. Furthermore, the QUE-based procedure has run-time that matches the fastest known algorithms on both fronts. Our analysis of Filter is through the classic regret bound of the multiplicative weights update method. This connection allows us to avoid the technical complications in previous works and improve upon the run-time analysis of a gradient-descent-based algorithm for robust mean estimation by Cheng, Diakonikolas, Ge and Soltanolkotabi (ICML '20).

Key facts. Cited by 44 papers in the map (data through 7 Oct 2026). First posted on arXiv 31 Jul 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 10; 2022: 12; 2023: 10; 2024: 6; 2025: 3; 2026: 3.

44 papers.

Sort:

  1. 2021Robust and Differentially Private Mean Estimationcited by 66
  2. 2021Differential privacy and robust statistics in high dimensionscited by 64
  3. 2021Smoothed Analysis with Adaptive Adversariescited by 57
  4. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  5. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  6. 2022Statistical, Robustness, and Computational Guarantees for Sliced Wasserstein Distancescited by 41
  7. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  8. 2022Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guaranteescited by 30
  9. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  10. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 23
  11. 2022Online Prediction in Sub-linear Spacecited by 16
  12. 2023Outlier-Robust Wasserstein DROcited by 16
32 more
  1. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  2. 2024Tolerant Algorithms for Learning with Arbitrary Covariate Shiftcited by 15
  3. 2021Outlier-Robust Sparse Estimation via Non-Convex Optimizationcited by 14
  4. 2022Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributionscited by 13
  5. 2022List-Decodable Sparse Mean Estimationcited by 11
  6. 2021Heavy-tailed Streaming Statistical Estimationcited by 10
  7. 2023Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCAcited by 10
  8. 2023Robust Estimation under the Wasserstein Distancecited by 8
  9. 2023Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regressioncited by 7
  10. 2023Time-Uniform Confidence Spheres for Means of Random Vectorscited by 6
  11. 2021Adversarial for Good? How the Adversarial ML Community's Values Impede Socially Beneficial Uses of Attackscited by 5
  12. 2022Efficient List-Decodable Regression using Batchescited by 5
  13. 2023Improved Space Bounds for Learning with Expertscited by 5
  14. 2024Robust Distribution Learning with Local and Global Adversarial Corruptionscited by 5
  15. 2024Efficient PAC Learning of Halfspaces with Constant Malicious Noise Ratecited by 5
  16. 2024Robust Gradient Descent for Phase Retrievalcited by 2
  17. 2024The Broader Landscape of Robustness in Algorithmic Statisticscited by 2
  18. 2021Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected Errorcited by 1
  19. 2023Attacking Byzantine Robust Aggregation in High Dimensionscited by 1
  20. 2025Communication Bounds for the Distributed Experts Problemcited by 1
  21. 2025Learning High-dimensional Gaussians from Censored Datacited by 1
  22. 2026Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexitycited by 1
  23. 2026Robust Moment-Based Estimation via Spectral Gradient Reweightingcited by 1
  24. 2022An Efficient Minimax Optimal Estimator For Multivariate Convex Regressioncited by 0
  25. 2022Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Modelscited by 0
  26. 2022A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance & heterogeneous noisecited by 0
  27. 2022Robustifying Markowitzcited by 0
  28. 2023Robust Mean Estimation Without Moments for Symmetric Distributionscited by 0
  29. 2023Statistical Barriers to Affine-equivariant Estimationcited by 0
  30. 2024Heavy-tailed Contamination is Easier than Adversarial Contaminationcited by 0
  31. 2025Robust Estimation Under Heterogeneous Corruption Ratescited by 0
  32. 2026Mean Testing under Truncation beyond Gaussiancited by 0