Robust Sparse Mean Estimation via Sum of Squares
share
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 ℝ^d with "certifiably bounded" t-th moments and sufficiently light tails, our algorithm achieves error of O(ϵ^1-1/t) with sample complexity m = (klog(d))^O(t)/ϵ^2-2/t. For the special case of the Gaussian distribution, our algorithm achieves near-optimal error of Õ(ϵ) with sample complexity m = O(k^4 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.
READ FULL TEXT