论文标题
列表可取消的稀疏平均估计
List-Decodable Sparse Mean Estimation
论文作者
论文摘要
稳健的平均估计是统计中最重要的问题之一：鉴于$ \ Mathbb {r}^d $中的一组样本，其中$α$分数从某些分布$ d $中得出，其余的则是对手损坏的，我们旨在估计$ d $的平均值。最近的一系列研究兴趣一直集中在可验证的环境上，其中$α\ in（0，\ frac12] $，目标是输出有限数量的估计值，其中至少一个近似于目标平均值。在本文中，我们认为基本的$ d $是$ k $ -sparse的均值。 $ o \ big（\ mathrm {poly}（k，\ log d）\ big）$，即尺寸中的poly-logarithmic。
Robust mean estimation is one of the most important problems in statistics: given a set of samples in $\mathbb{R}^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 $α\in (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\big(\mathrm{poly}(k, \log d)\big)$, 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.
