List-Decodable Sparse Mean Estimation

Shiwei Zeng, Jie Shen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

Robust mean estimation is one of the most important problems in statistics: given a set of samples in Rd 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 α 2 (0, 1/2], 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))z 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.

Original languageEnglish
Title of host publicationAdvances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022
EditorsS. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, A. Oh
ISBN (Electronic)9781713871088
StatePublished - 2022
Event36th Conference on Neural Information Processing Systems, NeurIPS 2022 - New Orleans, United States
Duration: 28 Nov 20229 Dec 2022

Publication series

NameAdvances in Neural Information Processing Systems
Volume35
ISSN (Print)1049-5258

Conference

Conference36th Conference on Neural Information Processing Systems, NeurIPS 2022
Country/TerritoryUnited States
CityNew Orleans
Period28/11/229/12/22

Fingerprint

Dive into the research topics of 'List-Decodable Sparse Mean Estimation'. Together they form a unique fingerprint.

Cite this