论文标题
使用任意异常值对高度不完整数据的稳健平均估计
Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers
论文作者
论文摘要
我们研究了$ n $示例的强有力估算$ d $维分布的平均值的问题，在此示例中，每个示例的大多数坐标都可能丢失，并且$ \ varepsilon n $示例可能会被任意损坏。假设每个坐标都以恒定因素出现超过$ \ varepsilon n $示例的示例，我们显示的算法可以通过理论上信息与最佳尺寸的错误错误保证在接近线性的时间$ \ widetilde o（nd）$中估算分布的平均值。我们的结果将有关计算效率的鲁棒估计的最新工作扩展到了更广泛的不完整数据设置。
We study the problem of robustly estimating the mean of a $d$-dimensional distribution given $N$ examples, where most coordinates of every example may be missing and $\varepsilon N$ examples may be arbitrarily corrupted. Assuming each coordinate appears in a constant factor more than $\varepsilon N$ examples, we show algorithms that estimate the mean of the distribution with information-theoretically optimal dimension-independent error guarantees in nearly-linear time $\widetilde O(Nd)$. Our results extend recent work on computationally-efficient robust estimation to a more widely applicable incomplete-data setting.
