Nov, 2017

混合模型、鲁棒性和平方和证明

PDF
TL;DR本文基于 Sum of Squares 方法，探讨了用于高维下学习高度分离的高斯混合物和鲁棒均值估计的新有效算法，进一步优化了以往算法的统计保障。通过在高度分离的高斯混合物和穿插噪音后的子高斯分布上实现均值估计，我们的方法多次突破优化算法的极限。
sum of squares methodgaussian mixturesmean estimationsub-gaussian distributionsdp
发现论文，激发创造
  • 任意可簇合高斯混合模型的鲁棒学习

    研究了在高维高斯混合假设下，少量数据受到对手损坏的情况下的高效可学习性，提出了一种多项式算法并证明了在成分经过配对后在总变异距离上分离时，该问题是可多项式学习的；这种算法是第一个可处理 $k=2$ 的高斯混合问题的多项式时间算法，并使用基于 Sum-of-Squares 证明算法的技术，提出了一种新的用于高斯混合的鲁棒可辨识性证明方法和使用 SoS 可证明的反集中方法和新的特征距离度量组来解决问题。

    May, 2020

  • 学习有界协方差高斯混合模型的 SQ 下界

    本论文研究了学习具有相同未知有界协方差矩阵的分离高斯混合模型的复杂性，证明了该问题的任何统计查询算法至少需要 d 的阶次 1/ε 的复杂度，这为已知算法的最佳性提供了证据。

    Jun, 2023

  • 基于平方和的异常值稳健矩估计

    在存在对抗离群值的情况下，我们开发了有效的算法来估计未知分布的低阶矩。这些算法的保证在许多情况下显著优于 Diakonikolas 等人、Lai 等人和 Charikar 等人的最佳先前算法，同时我们还展示了这些算法的保证与我们考虑的分布类别的信息论下界相匹配，这些改进的保证使我们能够在存在离群值的情况下提供改进的独立成分分析和学习混合高斯的算法，我们的算法基于对下面概念简单优化问题的标准平方和松弛：在所有矩与未知分布相同的分布中，找到与对抗性污染样本的经验分布在统计距离上最接近的分布。

    Nov, 2017

  • 非球形混合物的异常值鲁棒聚类

    本研究提出了一种新的检测离群值的高效算法，用于聚类混合的高斯模型，这种方法是鲁棒的，可以处理在数据中有少部分的失真或错误，它依赖于 TV 距离和方差有限度等假定条件，并使用极小化两种偏差的方法来修复度量误差和离群值异常。

    May, 2020

  • 高斯混合模型的强健可学习性

    本文介绍了学习高斯混合分布和算法鲁棒性统计的自然融合，提出了第一个可靠的算法，用于学习任意数量的高斯混合物，且仅需要混合权重（有界分数性）和成分之间的总变差距离与零保持一定距离的温和假设条件。算法的核心是一种新的方法，通过对某些生成函数应用一系列精心选择的微分运算来证明维度无关的多项式可辨识性，这些生成函数不仅编码了我们想要学习的参数，还编码了我们想要解决的多项式方程系统。我们展示了如何直接使用我们推导出的符号身份来分析自然的平方和松弛问题。

    Nov, 2020

  • 稳健地学习 $k$ 个任意高斯分布的混合

    在固定 $k$ 个任意高斯分布的混合物和常量级别的数据污染的情况下，我们提出了一个用于稳健估计的多项式时间算法。该算法的主要工具有基于平方和方法的有效局部聚类算法和允许 Frobenius 范数和低秩项误差的新型张量分解算法。

    Dec, 2020

  • 高维高斯分布和高斯混合模型的鲁棒估计的统计查询下限

    本文提出了一种统计查询下限技术，用于解决高维学习问题中高斯分布的学习和鲁棒性学习问题，并得出了样本复杂度和计算复杂度之间存在的超多项式差距，同时提供了一个新的方法来解决一些相关的无监督估计和测试问题。

    Nov, 2016

  • 球形高斯混合物的近最优样本估计器

    提供了一种高效的样本多项式时间估计器，用于高维球形高斯混合模型中，从而显着降低了时间和样本复杂度，并且还提出了针对一维混合模型的简单估计器及一种更快的算法，用于从一组分布中选择密度估计。

    Feb, 2014

  • 学习线性分类器混合模型的 SQ 下界

    学习高斯协变量下的线性分类器混合问题，主要结果是一个统计查询（SQ）下界暗示已知算法对于该问题基本上是最佳的，甚至对于均匀混合的特殊情况。

    Oct, 2023

  • 球形高斯混合物的列表可解鲁棒均值估计与学习

    使用多项式技术来移除高维数据集中的异常值，同时提出了非常有效的算法，大大改进了高斯均值估计和学习混合球形高斯问题的保障性能。

    Nov, 2017