List-Decodable Sparse Mean Estimation

Nov 28, 2022

Speakers

About

Robust mean estimation is one of the most important problems in statistics: given a set of samples {x_1, ..., x_n}⊂ℝ^d where an α fraction are drawn from some distribution D and the rest are adversarially corrupted, it aims to estimate the mean of D. A surge of recent research interest has been focusing on the list-decodable setting where α∈ (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 is Gaussian and the target mean is k-sparse. 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 the main algorithmic ingredients is using low-degree sparse polynomials to filter outliers, which may be of independent interest.

Organizer

Store presentation

Should this presentation be stored for 1000 years?

How do we store presentations

Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%

Sharing

Recommended Videos

Presentations on similar topic, category or speaker

Interested in talks like this? Follow NeurIPS 2022