Related papers: Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions

Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions

URL: http://arxiv.org/abs/2211.16333v1
Date: Tue, 29 Nov 2022 16:13:50 GMT
Title: Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions
Authors: Ilias Diakonikolas, Daniel M. Kane, Jasper C.H. Lee, Ankit Pensia
Abstract summary: Given a small number of corrupted samples, the goal is to efficiently compute a hypothesis that accurately approximates $mu$ with high probability. Our algorithm achieves the optimal error using a number of samples scaling logarithmically with the ambient dimension. Our analysis may be of independent interest, involving the delicate design of a (non-spectral) decomposition for positive semi-definite satisfying certain sparsity properties.
Score: 42.6763105645717
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: 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 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.