11 月 13 日，微软研究院（Microsoft Research）和普林斯顿大学研究人员，提出了一个通用框架，用于设计无监督学习问题的有效算法，如高斯分布和子空间聚类的混合。
研究人员所提的框架在解决噪声问题上，使用了一种下界学习计算公式的元算法。这是建立在 Garg、Kayal 和 Saha (FOCS ’20) 最近的工作基础上的，他们设计了这样一个框架，用于在没有任何噪音的情况下学习算术公式。元算法的一个关键要素是针对称为“稳健向量空间分解”的新问题的有效算法。
研究证明，当某些矩阵具有足够大的最小非零奇异值时，元算法效果很好。“我们推测这个条件适用于我们问题的平滑实例，因此我们的框架将为平滑设置中的这些问题产生有效的算法。”
该研究以《在存在噪声的情况下学习算术公式：无监督学习的通用框架和应用》（Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning）为题，于 11 月 13 日发布在 arXiv 预印平台上。
无监督学习涉及发现数据中隐藏的模式和结构，而不使用任何标签或直接的人类监督。
在这里，研究人员考虑具有良好数学结构或从数学上明确定义的分布生成的数据。前者的一个例子是，可以根据某些相似性模式将数据点分组为有意义的集群，并且目标是找到底层集群。后者的一个例子是混合建模，它假设数据是由简洁描述的概率分布（例如高斯分布）的混合生成的，目标是从样本中学习这些分布的参数。
解决许多无监督学习问题的通用框架是矩方法，它利用数据的统计矩来推断模型的底层结构或底层参数。对于许多无监督学习问题场景，其中基础数据具有一些很好的数学结构，数据的矩是参数的明确定义的函数。启发式论证表明，相反的情况通常应该成立，即结构/分布的参数通常由数据的一些低阶矩唯一确定。在这个大方向上，主要的挑战是设计算法来（近似地）从（经验）力矩中恢复潜在的参数。
我们还希望该算法高效、耐噪声（即，即使仅近似而不是精确地知道矩，也能很好地工作），甚至是异常容忍度(即，即使少数数据点不符合底层结构/分布也能很好地工作)。但即使是该领域最简单的问题也往往是 NP 困难的，并且即使没有噪声和异常值也仍然如此。
因此，人们实际上不能指望一种具有可证明的最坏情况保证的算法。但人们可以希望算法能够保证通常运行良好，即对于随机问题实例，或者更理想的是对于以平滑方式选择的实例。因此，针对无监督学习中的每个此类问题设计了许多不同的算法，具有不同水平的效率、噪声容忍度、离群值容忍度和可证明的保证。
在这项工作中，研究人员给出了一个适用于许多此类无监督学习问题的元算法。该研究的出发点是观察到许多此类问题都归结为学习算术公式的适当子类的任务。
