ACM通信
研究突出了
技术视角:稳健统计解决新问题
下面的论文代表了关于高维稳健统计的漫长而富有成效的工作的开始。尽管人们对稳健统计的研究由来已久，至少可以追溯到杜克，6最近的复兴集中在算法问题上，这些问题在早期的统计工作中基本上没有得到解决。
健壮统计的核心问题是如何从可能以某种方式损坏的数据中提取信息。最常见的健壮性形式(这里也考虑到)是对的健壮性离群值部分数据已被删除，代之以任意的错误点。稳健统计的一个常见实例是使用中位数而不是平均值，因为中位数对极端点不太敏感，而相反，单个过大的值可能完全扭曲平均值。
中值到更高维度有几种推广方法，每种方法都有自己的鲁棒性。其中包括几何中位数(找到与输入数据集的欧氏平均距离最小的点)和Tukey中位数(找到数据集中“最深”的点)。然而，当维数较大时，几何中值是脆弱的，而Tukey中值是np -难计算的。一般来说，在较老的统计文献中，没有既能有效计算又能在高维环境下良好工作的估计器，尽管Donoho1多诺霍和加斯科2确实为这个目标构建了几个估计器，它们的思想至今仍有意义。
这就引出了Diakonikolas等人目前的一篇论文，该论文为包括高斯函数的鲁棒均值估计在内的几个问题构造了有效的鲁棒估计。对于这个问题，所有先前的鲁棒估计要么在高维上有不利的误差，要么不能在多项式时间内计算(Lai等人的并发工作)。5还提出了一个边界稍差的多项式时间估计器;以及Klivans等人早期的研究。4介绍了鲁棒分类的相关思想)。
虽然有许多变体，但本文中的两个关键技术是许多结果的基础。第一种是“过滤算法”，在后续的工作中最常使用。基本的想法是检查你的分布是否有一些理想的特性(如有界协方差)，这样如果有，我们就可以直接执行稳健恢复。如果属性保持不变，那么我们就完成了;否则，我们希望财产被侵犯的证明能让我们“过滤掉”不好的地方，然后再试一次。通过这种方式，我们最终必须成功:我们所期望的属性将最终保持不变，因为糟糕的点只有有限的数量。
第二种方法为某一凸程序构造“近似分离预言”，从而近似求解凸程序得到准确的鲁棒估计。扭转是凸程序取决于我们首先应该估计的数量!但这就是近似分离预言的由来——事实证明，在不知道量本身的情况下，也可以构建这个分离预言。这种特殊的技术没有像滤波算法那样得到广泛应用，但与后来的思想如朱等人的非凸分析有精神上的联系。7
本文针对几个问题构造了有效的鲁棒估计，包括高斯函数的鲁棒均值估计。
从这些早期论文开始，研究人员探索了许多算法问题，包括鲁棒分类和回归、列表解码模型中的鲁棒性、鲁棒性的平方和证明以及鲁棒恢复的非凸优化。最近的工作也超越了算法问题，挖掘出新的统计见解，例如在相当弱的统计假设下工作的新估计量，Donoho和Liu介绍的最小距离泛函的联系，3.以及对交通指标定义的新形式腐败的鲁棒性。
对于那些有兴趣了解更多的人，现在有一些关于这些主题的教程、展览和课程，包括其中一位作者的论文、华盛顿大学的一门相关课程和我自己的课堂笔记。
参考文献
2.多诺霍，D.L.和Gasko, M.基于半空间深度和投影离群的位置估计的分解性质。统计年鉴20,4(1992)，1803-1827。
3.最小距离泛函的“自动”鲁棒性。统计年鉴16， 2(1988)， 552-586。
4.Klivans, A.R, Long, P.M.和Servedio, R.A.学习带有恶意噪声的半空间。J. ML研究10(2009), 2715 - 2740。
5.Lai, k.a.， Rao, A.B.和Vempala, S.均值和协方差的不可知论估计。计算机科学基础, 2016年。
数字图书馆是由计算机协会出版的。版权所有©2021 ACM, Inc.
没有发现记录