Outlier-Robust Clustering of Non-Spherical Mixtures
Outlier-Robust Clustering of Non-Spherical Mixtures
复制标题
非球形混合物的异常值稳健聚类
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Pravesh Kothari
中科院分区：
文献类型：
--
作者：
Ainesh Bakshi;Pravesh Kothari
我们给出了第一个孤立点稳健的高效算法，用于对$k$统计分离的d维高斯(k-GMM)的混合进行聚类。具体地说，我们的算法从$k$-GMM和$d^{\Text{Poly}(k/\eta)}$时间中输入一个$epsilon$-损坏的样本，输出一个近似聚类，当每对混合成分以总变差(TV)距离$1-\exp(-\Text{Poly}(k/\eta)^k)$分隔时，该近似聚类至多错误分类$k^{O(K)}(\epsilon+\eta)$分数的点。这样的结果以前是未知的，甚至对于$k=2$也是如此。TV分离是统计上最弱的分离概念，它捕获了重要的特殊情况，如混合线性回归和子空间聚类。
我们在概念上的主要贡献是提取了两个简单的分析性质-(可证明的)超收缩和反集中-这是混合模型(有效)可聚类的必要条件和充分条件。因此，我们的结果推广到了对单位球面上均匀分布的任意仿射变换的混合进行聚类。在我们的工作之前，即使是满足这两个分析假设的分离分布的信息理论聚集性也是未知的，并且可能是独立感兴趣的。
我们的算法建立在最近的一系列工作基础上，这些工作依赖于[KKK‘19，RY’20]中首次引入的可证明的反浓度。我们的技术扩展了平方和工具包，以显示数据中电视分离的高斯簇的稳健可证明性。这涉及到通过仅依靠超收缩和反集中来给出将参数(即均值和协方差)距离与总变化距离联系起来的陈述的低次平方和证明。
We give the first outlier-robust efficient algorithm for clustering a mixture of $k$ statistically separated d-dimensional Gaussians (k-GMMs). Concretely, our algorithm takes input an $\epsilon$-corrupted sample from a $k$-GMM and whp in $d^{\text{poly}(k/\eta)}$ time, outputs an approximate clustering that misclassifies at most $k^{O(k)}(\epsilon+\eta)$ fraction of the points whenever every pair of mixture components are separated by $1-\exp(-\text{poly}(k/\eta)^k)$ in total variation (TV) distance. Such a result was not previously known even for $k=2$. TV separation is the statistically weakest possible notion of separation and captures important special cases such as mixed linear regression and subspace clustering.
Our main conceptual contribution is to distill two simple analytic properties - (certifiable) hypercontractivity and anti-concentration - that are necessary and sufficient for mixture models to be (efficiently) clusterable. As a consequence, our results extend to clustering mixtures of arbitrary affine transforms of the uniform distribution on the $d$-dimensional unit sphere. Even the information theoretic clusterability of separated distributions satisfying these two analytic assumptions was not known prior to our work and is likely to be of independent interest.
Our algorithms build on the recent sequence of works relying on certifiable anti-concentration first introduced in [KKK'19,RY'20]. Our techniques expand the sum-of-squares toolkit to show robust certifiability of TV-separated Gaussian clusters in data. This involves giving a low-degree sum-of-squares proof of statements that relate parameter (i.e. mean and covariances) distance to total variation distance by relying only on hypercontractivity and anti-concentration.
登录
查看更多内容
列表可解码线性回归
DOI：
--
发表时间：
2019
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Karmalkar, Sushrut;Klivans, Adam;Kothari, Pravesh
通讯作者：
Kothari, Pravesh
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.1137/1.9781611975031.171
发表时间：
2017-04
期刊：
ArXiv
影响因子：
--
作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
通讯作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
DOI：
--
发表时间：
2017-03
期刊：
--
影响因子：
--
作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
通讯作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart