Robustly learning mixtures of k arbitrary Gaussians
Robustly learning mixtures of k arbitrary Gaussians
复制标题
鲁棒地学习 k 个任意高斯的混合
DOI：
10.1145/3519935.3519953
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Vempala, Santosh S.
中科院分区：
文献类型：
--
作者：
Bakshi, Ainesh;Diakonikolas, Ilias;Jia, He;Kane, Daniel M.;Kothari, Pravesh K.;Vempala, Santosh S.
我们给出了一个多项式时间算法的问题的鲁棒估计的混合ofkarbitrary Gaussians在pwd，对于任何固定的k，在存在一个常数分数的任意腐败。这解决了算法的鲁棒统计，解决了鲁棒估计（a）一个单一的高斯，（B）一个混合的TV距离分离高斯，（c）一个均匀的混合两个高斯的特殊情况下，在以前的几个作品中的主要公开问题。我们的主要工具是一个高效的部分聚类算法，依赖于平方和方法，和一个新的张量分解算法，允许错误的Frobenius范数和低秩项。
We give a polynomial-time algorithm for the problem of robustly estimating a mixture ofkarbitrary Gaussians in ℝd, for any fixedk, in the presence of a constant fraction of arbitrary corruptions. This resolves the main open problem in several previous works on algorithmic robust statistics, which addressed the special cases of robustly estimating (a) a single Gaussian, (b) a mixture of TV-distance separated Gaussians, and (c) a uniform mixture of two Gaussians. Our main tools are an efficientpartial clusteringalgorithm that relies on the sum-of-squares method, and a noveltensor decompositionalgorithm that allows errors in both Frobenius norm and low-rank terms.
登录
查看更多内容
列表可解码线性回归
DOI：
--
发表时间：
2019
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Karmalkar, Sushrut;Klivans, Adam;Kothari, Pravesh
通讯作者：
Kothari, Pravesh
通过平方和进行异常值稳健矩估计
DOI：
--
发表时间：
2017
期刊：
arXiv.org
影响因子：
--
作者：
Pravesh Kothari;David Steurer
通讯作者：
David Steurer
非球形混合物的异常值稳健聚类
DOI：
--
发表时间：
2020
期刊：
arXiv.org
影响因子：
--
作者：
Ainesh Bakshi;Pravesh Kothari
通讯作者：
Pravesh Kothari
DOI：
10.1145/3188745.3188758
发表时间：
2017-11
期刊：
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Ilias Diakonikolas;D. Kane;Alistair Stewart
通讯作者：
Ilias Diakonikolas;D. Kane;Alistair Stewart
鲁棒推理:基于影响函数的方法
DOI：
10.1016/s0169-7161(97)15005-2
发表时间：
1996
期刊：
Handbook of Statistics
影响因子：
--
作者：
M. Markatou;E. Ronchetti
通讯作者：
E. Ronchetti