A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation

We study the algorithmic problem of sparse mean estimation in the presence of adversarial outliers. Specifically, the algorithm observes a corrupted set of samples from N(μ,Id), where the unknown mean μ ∈ Rᵈ is constrained to be k-sparse. A series of prior works has developed efficient algorithms for robust sparse mean estimation with sample complexity poly(k,log d, 1/ε) and runtime d² poly(k,log d,1/ε), where ε is the fraction of contamination. In particular, the fastest runtime of existing algorithms is quadratic (Ω(d²)), which can be prohibitive in high dimensions. This quadratic barrier in the runtime stems from the reliance of these algorithms on the sample covariance matrix, which is of size d². Our main contribution is an algorithm for robust sparse mean estimation which runs in subquadratic time using poly(k,log d,1/ε) samples. We also provide analogous results for robust sparse PCA. Our results build on algorithmic advances in detecting weak correlations, a generalized version of the light-bulb problem by Valiant.