10,000+ 倍加速的鲁棒子集选择（ARSS）

从大规模带噪声数据中选择子集在各种应用中越来越受欢迎。然而，这一问题仍然极具挑战性，因为现有方法通常速度较慢且对异常值敏感。为了解决上述两个问题，我们提出了一种加速鲁棒子集选择（ARSS）方法。具体而言，在子集选择领域，这是首次尝试使用基于 $\ell_{p}(0<p\leq1)$ 范数的度量来表示损失，从而防止大误差主导我们的目标函数。因此，该方法对异常值元素的鲁棒性得到了显著增强。实际上，数据规模通常远大于特征长度，即 $N \gg L$。基于这一观察，我们提出了一种加速求解器（通过交替方向乘子法（ALM）和等价推导），以大幅降低计算成本，理论上从 $O(N^4)$ 降至 $O(N^2L)$。在十个基准数据集上的大量实验验证了我们的方法不仅优于现有最先进方法，而且比相关性最高的方法快 10,000 倍以上。