用于稳健稀疏平均估计的亚二次时间算法

我们研究在对抗性异常值存在下的稀疏平均估计的算法问题。具体来说，该算法会观察来自 N (, Id) 的一组损坏样本，其中未知均值 Rᵈ 受到 k-sparse 的限制。以往的一系列研究为稳健稀疏平均估计开发了有效的算法，具有样本复杂度 poly (k, d, 1/) 和运行时间 d² poly (k, d, 1/)，其中是污染的比例。特别是，现有算法的最快运行时间是二次的 ( (d²) )，这在高维度下可能是不可承受的。这种运行时间的二次障碍源于这些算法对样本协方差矩阵的依赖，样本协方差矩阵的大小为 d²。我们的主要贡献是一个在使用 poly (k, d, 1/) 样本的情况下运行在亚二次时间内的稳健稀疏平均估计算法。我们还为稳健稀疏 PCA 提供类似的结果。我们的结果基于检测弱相关性的算法进展，即 Valiant 所提出的灯泡问题的广义版本。