Mar, 2024
Huber 污染下高斯稀疏估计的鲁棒性优化错误
Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, Thanasis Pittas
TL;DR高斯稀疏估计在 Huber 污染模型中研究，针对均值估计、主成分分析和线性回归三个任务，提出了第一个样本和计算高效的鲁棒估计器，保证了较小的误差，并且在常数因子内达到最优。之前针对这些任务的高效算法都产生了数量上次优的误差。具体而言，对于高斯的鲁棒 k 稀疏均值估计在具有污染率为 ε>0 的 R^d 上，我们的算法具有样本复杂度为 (k^2/ε^2)・polylog (d/ε)，在多项式时间内运行，并且在 L2 误差为 O (ε) 的范围内逼近目标均值。之前的高效算法固有地产生了误差 Ω(ε√log (1/ε))。在技术层面上，我们开发了一种在稀疏情况下的新型多维过滤方法，可能具有其他应用。