Lattice-Based Methods Surpass Sum-of-Squares in Clustering
Lattice-Based Methods Surpass Sum-of-Squares in Clustering
复制标题
DOI：
--
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Ilias Zadik;M. Song;Alexander S. Wein;Joan Bruna
中科院分区：
文献类型：
--
作者：
Ilias Zadik;M. Song;Alexander S. Wein;Joan Bruna
聚类是无监督学习中的一个基本要素，它产生了大量具有计算挑战性的推理任务。在这项工作中，我们重点关注对具有未知（并且可能退化）协方差的d维高斯混合物进行聚类的典型任务。最近的工作（Ghosh等人'20; Mao，Wein' 21; Davis，迪亚兹，Wang '21）已经建立了针对低次多项式方法类的下界和用于恢复高斯聚类实例中植入的某些隐藏结构的平方和（SoS）层次结构。许多类似的推理任务的先前工作预示着，这样的下限强烈建议存在一个固有的算法到计算的差距聚类，也就是说，参数制度的聚类任务是统计上可能的，但没有多项式时间算法成功。我们考虑的聚类任务的一个特殊情况相当于在一个随机子空间中找到一个种植超立方体向量的问题。我们发现，也许令人惊讶的是，这种特定的聚类模型并没有表现出计算的差距，即使在这种情况下，上述低程度和SoS的下限继续适用。为了实现这一点，我们给出了一个多项式时间算法的基础上的Lenstra-Lenstra-Lovasz格基减少方法，实现了最佳的样本复杂度d +1个样本。这一结果扩展了一类问题，其被限制的计算到计算的差距可以通过"脆性"多项式时间算法"关闭"，突出了噪声在计算到计算的差距的发病中的关键但微妙的作用。
Clustering is a fundamental primitive in unsupervised learning which gives rise to a rich class of computationally-challenging inference tasks. In this work, we focus on the canonical task of clustering d-dimensional Gaussian mixtures with unknown (and possibly degenerate) covariance. Recent works (Ghosh et al. '20; Mao, Wein '21; Davis, Diaz, Wang '21) have established lower bounds against the class of low-degree polynomial methods and the sum-of-squares (SoS) hierarchy for recovering certain hidden structures planted in Gaussian clustering instances. Prior work on many similar inference tasks portends that such lower bounds strongly suggest the presence of an inherent statistical-to-computational gap for clustering, that is, a parameter regime where the clustering task is statistically possible but no polynomial-time algorithm succeeds. One special case of the clustering task we consider is equivalent to the problem of finding a planted hypercube vector in an otherwise random subspace. We show that, perhaps surprisingly, this particular clustering model does not exhibit a statistical-to-computational gap, even though the aforementioned low-degree and SoS lower bounds continue to apply in this case. To achieve this, we give a polynomial-time algorithm based on the Lenstra--Lenstra--Lovasz lattice basis reduction method which achieves the statistically-optimal sample complexity of d+1 samples. This result extends the class of problems whose conjectured statistical-to-computational gaps can be"closed"by"brittle"polynomial-time algorithms, highlighting the crucial but subtle role of noise in the onset of statistical-to-computational gaps.