A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation

arXiv:2403.04726v1 Announce Type: cross
Abstract: We study the algorithmic problem of sparse mean estimation in the presence of adversarial outliers. Specifically, the algorithm observes a \emph{corrupted} set of samples from $\mathcal{N}(\mu,\mathbf{I}_d)$, where the unknown mean $\mu \in \mathbb{R}^d$ is constrained to be $k$-sparse. A series of prior works has developed efficient algorithms for robust sparse mean estimation with sample complexity $\mathrm{poly}(k,\log d, 1/\epsilon)$ and runtime $d^2 \mathrm{poly}(k,\log d,1/\epsilon)$, where $\epsilon$ is the fraction of contamination. In particular, the fastest runtime …

abstract adversarial algorithm arxiv cs.ds cs.lg math.st mean outliers prior robust samples series set stat.ml stat.th study the algorithm the unknown type