2022/05/28 by Shiwei Zeng, Jie Shen, Zeng, Shiwei +1 · 3 citations
Computer Science · #FOS: Computer and information sciences #Machine Learning (cs.LG) #cs.LG
paper · pdf · doi:10.48550/arxiv.2205.14337
v2 introduces low-degree polynomials to improve error rate, and is accepted to NeurIPS 2022
arxiv created 2022/12/05 · arxiv updated 2022/12/07
Robust mean estimation is one of the most important problems in statistics: given a set of samples in ℝd where an α fraction are drawn from some distribution D and the rest are adversarially corrupted, we aim to estimate the mean of D. A surge of recent research interest has been focusing on the list-decodable setting where α∈ (0, \frac12], and the goal is to output a finite number of estimates among which at least one approximates the target mean. In this paper, we consider that the underlying distribution D is Gaussian with k-sparse mean. Our main contribution is the first polynomial-time algorithm that enjoys sample complexity O(poly(k, log d)), i.e. poly-logarithmic in the dimension. One of our core algorithmic ingredients is using low-degree sparse polynomials to filter outliers, which may find more applications.