Timezone: »

 
Poster
Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions
Ilias Diakonikolas · Daniel Kane · Jasper Lee · Ankit Pensia

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #729
in Poster Session 1 »
We study the fundamental task of outlier-robust mean estimation for heavy-tailed distributions in the presence of sparsity. Specifically, given a small number of corrupted samples from a high-dimensional heavy-tailed distribution whose mean $\mu$ is guaranteed to be sparse, the goal is to efficiently compute a hypothesis that accurately approximates $\mu$ with high probability. Prior work had obtained efficient algorithms for robust sparse mean estimation of light-tailed distributions. In this work, we give the first sample-efficient and polynomial-time robust sparse mean estimator for heavy-tailed distributions under mild moment assumptions. Our algorithm achieves the optimal asymptotic error using a number of samples scaling logarithmically with the ambient dimension. Importantly, the sample complexity of our method is optimal as a function of the failure probability $\tau$, having an {\em additive} $\log(1/\tau)$ dependence. Our algorithm leverages the stability-based approach from the algorithmic robust statistics literature, with crucial (and necessary) adaptations required in our setting. Our analysis may be of independent interest, involving the delicate design of a (non-spectral) decomposition for positive semi-definite matrices satisfying certain sparsity properties.
Keywords: robust statistics · sparse estimation · heavy-tailed estimation
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Ilias Diakonikolas (University of Wisconsin-Madison)
Daniel Kane (UCSD)
Jasper Lee (University of Wisconsin-Madison)
Ankit Pensia (University of Wisconsin-Madison)

More from the Same Authors