May, 2023

相对 Frobenius 范数下的可列表解协方差估计的谱算法

PDF
TL;DR研究列表可解的高斯协方差估计问题，提出了基于谱技术的多滤波方法，解决了高斯混合模型偏差聚类的问题并得到了最新 GMM 学习方法的解。
list-decodable gaussian covariance estimationspectral techniquespartial clusteringgaussian mixture modelssum-of-squares-free algorithm
发现论文，激发创造
  • 球形高斯混合物的列表可解鲁棒均值估计与学习

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

    Nov, 2017

  • 具有亚高斯速率的均值估计的快速谱算法

    研究估计具有有界平均值和协方差的重尾随机向量均值的算法问题，提供了一种基于谱方法的算法来解决该问题，并且只需要计算近似特征向量，取得了最优的统计性能和更快的运行速度。

    Aug, 2019

  • 列表可解线性回归

    该研究为第一篇在 list-decodable 设置中，给出了一种鲁棒的回归问题的多项式时间算法，当假设内点分布是 certifiably anti-concentrated 分布时，该算法能够成功地给出一个接近于真解的目标函数。

    May, 2019

  • 高维稳健协方差估计的快速算法

    本文研究了协方差矩阵的估计问题，当仅有小部分样本被恶意更改时，我们提出了一种运行时间接近计算经验协方差且具有最佳误差保证的算法，该算法适用于高维分布，能处理高斯分布等深度分布结构及矩阵乘法指数中的病态情形。

    Jun, 2019

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

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

    Jul, 2020

  • 通过平方和实现列表可解码学习

    研究通过 Sum-of-Squares SDP hierarchy 在列表可解码学习上的应用，分别对线性回归和均值估计问题进行了研究，并提出了新的算法来解决这些问题，其中输入数据中包含了异常值。

    May, 2019

  • 重尾统计算法：回归、协方差估计和更多

    研究怎样在不假设样本的基础分布为高斯分布的前提下，只假定有限个矩的情况下，有效地进行线性回归和协方差估计，并关注能用多少样本来实现高精度和指数级成功概率。使用八阶圆当量半定规划提供算法，预备性的证据表明在我们的算法使用的平均中位数框架中无法在多项式时间内改善这些误差率。

    Dec, 2019

  • 稳健稀疏均值估计的次二次时间算法

    稀疏均值估计算法在存在对抗性异常值的情况下的研究，提出了一种在次二次时间内运行的鲁棒稀疏均值估计算法，并在检测弱相关性方面取得了算法进展。

    Mar, 2024

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

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

    Jun, 2023

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

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

    Nov, 2017