Nov, 2017

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

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

    本文基于 Sum of Squares 方法，探讨了用于高维下学习高度分离的高斯混合物和鲁棒均值估计的新有效算法，进一步优化了以往算法的统计保障。通过在高度分离的高斯混合物和穿插噪音后的子高斯分布上实现均值估计，我们的方法多次突破优化算法的极限。

    Nov, 2017

  • 稳定凸松弛法私有鲁棒估计

    提出了一种新的框架，以将鲁棒性的凸松弛算法修改为满足适当参数规范的强最坏情况稳定性保证。通过这一框架，提出了一个可以在存在恶意数据干扰下实现微分隐私的高阶矩的鲁棒估计的算法，包括均值和协方差的估计。该算法成功地应用于成族分布，并在适当参数范数下提供恢复和维度参数的从容保证。

    Dec, 2021

  • 对异常数据鲁棒的回归的高效算法

    本文首次给出了一个多项式时间算法，用于在示例和标签中对抗性堕落下执行线性或多项式回归，并基于 SoS 方法提出了一种自然的凸松弛方法来解决非凸优化问题。

    Mar, 2018

  • 使用亚高斯率的光谱算法进行稳健回归

    本论文研究线性回归问题并提出了一种新的算法，它能够在存在离群值的情况下，对有限矩（至 $L_4$）的样本进行最佳的次高斯误差边界估计，并且通过使用谱方法研究了线性回归问题与最远超平面问题之间的关系，同时引入了第三个经验过程进行统计学属性的研究。

    Jul, 2020

  • 通过放松张量范数实现更好的不可知聚类

    基于平方和范数的 $k$-means 聚类的凸松弛算法及其学习算法，能够学习高斯混合物的均值。

    Nov, 2017

  • 任意可簇合高斯混合模型的鲁棒学习

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

    May, 2020

  • 高斯混合模型的最优估计：去噪矩方法

    利用半定规划抑噪，解决高斯混合模型中方法矩的不一致性等问题，建立在 Wasserstein 距离下新的矩比较定理，提出新的算法，解决方法矩估计常见的问题。

    Jul, 2018

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

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

    May, 2020

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

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

    Nov, 2016

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

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

    Nov, 2020