【斯坦福大学博士论文】鲁棒学习:信息论和算法，88页pdf

2022 年 11 月 13 日 专知

本文概述了我和我的合作者在鲁棒估计方面的最新成果。关键问题如下:给定一个数据集，其中的一部分由任意离群点组成，我们能从非离群点中了解到什么? 这是一个经典的问题，至少可以追溯到Tukey(1960)。然而，由于种种原因，这个问题最近重新引起了人们的兴趣。首先，许多旧的结果在高维中没有给出有意义的误差边界(例如，在d维中误差通常包含隐式的√d因子)。随着机器学习越来越多地用于高维模型，这需要重新研究。其次，在Charikar等人(2017)中，我们建立了鲁棒估计与其他问题之间的联系，如聚类和随机块模型的学习。目前，聚类高斯混合的最佳已知结果是通过这些鲁棒的估计技术(Diakonikolas等人，2018b;Kothari和Steinhardt, 2018;Hopkins and Li, 2018)。最后，具有结构化异常值的高维生物数据集，如批处理效应(Johnson et al.， 2007;Leek等人，2010)，以及对机器学习系统的安全担忧(Steinhardt等人，2017)，从应用方向促进了对最坏情况异常值的鲁棒性研究。

https://cs.stanford.edu/~jsteinhardt/publications/thesis/paper.pdf

最近的研究显示，在这些问题上取得了令人鼓舞的进展，但快速的进展导致了文献的不透明。大多数论文单独来看是复杂的，但实际上是由几个关键主题的变化组成的。这篇论文的目的是提供一个易于理解的介绍，以突出主要技术的领域。在第一章中，我们介绍了鲁棒估计的基本问题，给出了在一维情况下的算法，为我们以后在高维情况下的算法做了铺垫，并解释了高维设置的基本难点。在第2章和第3章中，我们关注信息理论的鲁棒性——什么时候有可能(忽略计算成本)在异常值存在的情况下恢复良好的参数估计?这里的情况简单得令人愉快，它基于一种称为弹性的属性，该属性度量点的小亚种群的影响。有趣的是，弹性允许我们恢复对均值的估计，即使大多数点都是异常值，假设我们允许输出多次猜测(所谓的列表可解码设置，最早由Balcan等人(2008)引入)。这一基本事实是鲁棒学习和聚类之间联系的基础，因为我们可以将每个单独的簇视为“好”点的总体，然后将其余簇中的点视为异常值。

在第4章中，我们将注意力转向计算效率算法。假设好的点有有限的协方差，我们可以恢复平均值的估计，误差只随着协方差矩阵的最大特征值增长(通常与维数无关)。其基本思想是，均值偏移超过一小部分的离群点，必然会在数据中产生大的变化方向，这可以通过经验协方差的特征分解来检测。我们展示了如何将这种均值估计结果推广到一般的m估计，只要损失函数的梯度具有有界协方差。最后，在第五章中，我们介绍了一种基于对偶性的替代计算方法。使用这种方法，我们可以找到一个大家族鞍点问题的近似最小化存在离群点。这允许我们恢复与第4章相似的平均估计结果，优点是即使大多数点是异常值，结果也保持不变。这将生成目前给出最佳已知边界的聚类算法。然而，第4章和第5章中的技术都在积极开发中。即使在明年，这两种技术都可能获得更强的效果。总之，我们将看到一个相对完整的关于鲁棒性的信息论视角，以及设计高效算法的两种方法。这些方法以一般的方式呈现，以至于该领域的许多关键结果都是简单的推论，通常只需要大约一页的代数来检查条件。我们希望通过揭示争论背后的结构，我们将使新的研究人员能够应用和扩展这些结果。