Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination

arXiv:2403.10416v1 Announce Type: new
Abstract: We study Gaussian sparse estimation tasks in Huber's contamination model with a focus on mean estimation, PCA, and linear regression. For each of these tasks, we give the first sample and computationally efficient robust estimators with optimal error guarantees, within constant factors. All prior efficient algorithms for these tasks incur quantitatively suboptimal error. Concretely, for Gaussian robust $k$-sparse mean estimation on $\mathbb{R}^d$ with corruption rate $\epsilon>0$, our algorithm has sample complexity $(k^2/\epsilon^2)\mathrm{polylog}(d/\epsilon)$, runs in sample …

abstract arxiv cs.ds cs.lg error focus linear linear regression math.st mean prior regression robust sample stat.ml stat.th study tasks type