Robust Sparse Mean Estimation via Sum of Squares
This addresses a fundamental problem in robust statistics for high-dimensional data analysis, providing efficient solutions with theoretical guarantees, though it builds incrementally on prior work by extending to unknown covariances.
The paper tackles robust sparse mean estimation in high dimensions with adversarial outliers, developing the first efficient algorithms without prior covariance knowledge, achieving error O(ε^{1-1/t}) for certifiably bounded distributions and near-optimal error Õ(ε) for Gaussians with sample complexities (k log(d))^{O(t)}/ε^{2-2/t} and O(k^4 polylog(d))/ε^2, respectively.
We study the problem of high-dimensional sparse mean estimation in the presence of an $ε$-fraction of adversarial outliers. Prior work obtained sample and computationally efficient algorithms for this task for identity-covariance subgaussian distributions. In this work, we develop the first efficient algorithms for robust sparse mean estimation without a priori knowledge of the covariance. For distributions on $\mathbb R^d$ with "certifiably bounded" $t$-th moments and sufficiently light tails, our algorithm achieves error of $O(ε^{1-1/t})$ with sample complexity $m = (k\log(d))^{O(t)}/ε^{2-2/t}$. For the special case of the Gaussian distribution, our algorithm achieves near-optimal error of $\tilde O(ε)$ with sample complexity $m = O(k^4 \mathrm{polylog}(d))/ε^2$. Our algorithms follow the Sum-of-Squares based, proofs to algorithms approach. We complement our upper bounds with Statistical Query and low-degree polynomial testing lower bounds, providing evidence that the sample-time-error tradeoffs achieved by our algorithms are qualitatively the best possible.