论文标题
$ k $ unutary高斯的强大学习混合物
Robustly Learning Mixtures of $k$ Arbitrary Gaussians
论文作者
论文摘要
我们给出了多项式时间算法，即在$ \ mathbb {r}^d $中，对于任何固定的$ k $，在持续不断的任意腐败的情况下，在$ \ mathbb {r}^d $中估算了$ k $ nutionary的高斯人的混合。这解决了以前几项有关算法鲁棒统计的作品的主要开放问题，该统计数据涉及（a）单个高斯，（b）电视距离分离的高斯人的特殊情况，以及（c）两种高斯人的均匀混合物。我们的主要工具是一种有效的\ emph {部分聚类}算法，该算法依赖于方形方法，而新颖的\ emph {tensor empomposition}算法允许在frobenius norm和低率术语中允许错误。
We give a polynomial-time algorithm for the problem of robustly estimating a mixture of $k$ arbitrary Gaussians in $\mathbb{R}^d$, for any fixed $k$, 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 efficient \emph{partial clustering} algorithm that relies on the sum-of-squares method, and a novel \emph{tensor decomposition} algorithm that allows errors in both Frobenius norm and low-rank terms.
