Robust Estimators in High Dimensions without the Computational Intractability abstract。

解决的问题

本文研究在不可知环境中高维分布学习，其中允许攻击者任意破坏样本的 epsilon-fraction.
即使在最基本的设置中，唯一已知的方法要么在计算上效率低下，要么因为误差保证中丢失了维度相关的因素。
因此提出以下问题：高维不可知分布学习在算法上是否可行？

本文工作

在本文的工作中，我们获得了第一个具有与维度无关的误差保证的高效计算算法，用于不可知地学习基本类的高维分布：

  • 单个高斯分布
  • 超立方体上的乘积分布
  • 两种乘积分布的混合（自然平衡条件下
  • 球形高斯分布

并且提出了三个算法：

  • 贪婪迭代算法，每次迭代过滤一些损坏的样本，通过计算修改后的样本协方差矩阵的最高绝对特征值来获得过滤器
  • 依赖凸编程的算法，为样本计算适当的权重，通过近似分离预言来进行异常值鉴别
  • 标准评估器：经验平均值 empirical average， 可能无法正确评估去掉了 epsilon-fraction 的异常样本，所以提出了新的浓缩边界