# How Hard Is Robust Mean Estimation?

arXiv: https://arxiv.org/abs/1903.07870 · HTML: https://mlsanity.com/paper/1903.07870/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2019.

## Built on by (most cited first, 16 of 16)

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [A Huber Loss Minimization Approach to Byzantine Robust Federated Learning](https://mlsanity.com/paper/2308.12581/) (2023)
- [Learning GMMs with Nearly Optimal Robustness Guarantees](https://mlsanity.com/paper/2104.09665/) (2021)
- [SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications](https://mlsanity.com/paper/2410.21194/) (2024)
- [Robustness Auditing for Linear Regression: To Singularity and Beyond](https://mlsanity.com/paper/2410.07916/) (2024)
- [Robust Distribution Learning with Local and Global Adversarial Corruptions](https://mlsanity.com/paper/2406.06509/) (2024)
- [Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms](https://mlsanity.com/paper/2201.12700/) (2022)
- [Adversarially robust clustering with optimality guarantees](https://mlsanity.com/paper/2306.09977/) (2023)
- [Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussians](https://mlsanity.com/paper/2301.09024/) (2023)
- [Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error](https://mlsanity.com/paper/2410.17230/) (2024)
- [Sample-Optimal Private Regression in Polynomial Time](https://mlsanity.com/paper/2503.24321/) (2025)
- [Robust Sparse Regression with Non-Isotropic Designs](https://mlsanity.com/paper/2410.23937/) (2024)
- [Robust Mean Estimation Without Moments for Symmetric Distributions](https://mlsanity.com/paper/2302.10844/) (2023)
- [Algorithms with Polynomially-Improved Approximation Factors for the 2 rightarrow q Norm, and Applications](https://mlsanity.com/paper/2605.25303/) (2026)

## Abstract (arXiv)

Robust mean estimation is the problem of estimating the mean μ ∈ ℝd of a d-dimensional distribution D from a list of independent samples, an ε-fraction of which have been arbitrarily corrupted by a malicious adversary. Recent algorithmic progress has resulted in the first polynomial-time algorithms which achieve dimension-independent rates of error: for instance, if D has covariance I, in polynomial-time one may find hatμ with |μ - hatμ| ≤ O(√ε). However, error rates achieved by current polynomial-time algorithms, while dimension-independent, are sub-optimal in many natural settings, such as when D is sub-Gaussian, or has bounded 4-th moments. In this work we give worst-case complexity-theoretic evidence that improving on the error rates of current polynomial-time algorithms for robust mean estimation may be computationally intractable in natural settings. We show that several natural approaches to improving error rates of current polynomial-time robust mean estimation algorithms would imply efficient algorithms for the small-set expansion problem, refuting Raghavendra and Steurer's small-set expansion hypothesis (so long as P neq NP). We also give the first direct reduction to the robust mean estimation problem, starting from a plausible but nonstandard variant of the small-set expansion problem.