Skip to yearly menu bar Skip to main content


Spotlight Poster

A Subquadratic Time Algorithm for Robust Sparse Mean Estimation

Ankit Pensia

Hall C 4-9 #2508

Abstract: 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 μRd 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,logd,1/ϵ) and runtime d2poly(k,logd,1/ϵ), where ϵ is the fraction of contamination. In particular, the fastest runtime of existing algorithms is quadratic in the dimension, 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 d2. Our main contribution is an algorithm for robust sparse mean estimation which runs in _subquadratic_ time using poly(k,logd,1/ϵ) samples. Our results build on algorithmic advances in detecting weak correlations, a generalized version of the light-bulb problem by Valiant (2015).

Chat is not available.