Outlier-robust Mean Estimation near the Breakdown Point via
Sum-of-Squares
Outlier-robust Mean Estimation near the Breakdown Point via
Sum-of-Squares
We revisit the problem of estimating the mean of a high-dimensional distribution in the presence of an $\varepsilon$-fraction of adversarial outliers. When $\varepsilon$ is at most some sufficiently small constant, previous works can achieve optimal error rate efficiently \cite{diakonikolas2018robustly, kothari2018robust}. As $\varepsilon$ approaches the breakdown point $\frac{1}{2}$, all previous algorithms …