Poster
List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering
Ilias Diakonikolas · Daniel Kane · Sushrut Karmalkar · Ankit Pensia · Thanasis Pittas
Hall J (level 1) #828
Keywords: [ robust statistics ] [ list-decoding ] [ high-dimensional inference ] [ sparse estimation ]
Abstract:
We study the problem of list-decodable sparse mean estimation. Specifically, for a parameter , we are given points in , of which are i.i.d. samples from a distribution with unknown -sparse mean . No assumptions are made on the remaining points, which form the majority of the dataset. The goal is to return a small list of candidates containing a vector such that is small. Prior work had studied the problem of list-decodable mean estimation in the dense setting. In this work, we develop a novel, conceptually simpler technique for list-decodable mean estimation. As the main application of our approach, we provide the first sample and computationally efficient algorithm for list-decodable sparse mean estimation. In particular, for distributions with certifiably bounded'' -th moments in -sparse directions and sufficiently light tails, our algorithm achieves error of with sample complexity and running time . For the special case of Gaussian inliers, our algorithm achieves the optimal error guarantee with quasi-polynomial complexity. We complement our upper bounds with nearly-matching statistical query and low-degree polynomial testing lower bounds.
Chat is not available.