标题： 在具有不断增加的聚类数和子矩阵的数量的植入问题和子矩阵定位中的统计计算权衡 显示英文标题

标题： Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices

摘要： 我们考虑两个密切相关的两个问题：已植入的聚类问题和次矩阵定位问题。 已植入的聚类问题假设随机图是基于某些潜在的节点簇生成的；任务是在给定图的情况下恢复这些簇。 次矩阵定位问题涉及在一个大的实数值随机矩阵内部定位隐藏的均值升高的次矩阵。 特别感兴趣的是这样一个设定：允许簇/子矩阵的数量随问题规模无界增长。 这些公式涵盖了几个经典的模型，如已植入的团问题、已植入的最密集子图问题、已植入的划分问题、已植入的着色问题和随机块模型，这些模型广泛用于研究社区检测和聚类/双聚类。 对于这两个问题，我们表明模型参数（簇/子矩阵大小、簇密度和子矩阵均值）的空间可以被划分为四个互不相交的区域，对应于统计复杂性和计算复杂性的递减：(1)\emph{不可能}区域，在此区域内所有算法都失败；(2)\emph{硬}区域，在此区域内计算量大的最大似然估计（MLE）成功；(3)\emph{简单的}区域，在此区域内多项式时间凸化MLE成功；(4)\emph{简单}区域，在此区域内简单的计数/阈值处理成功。 此外，我们证明了每个这些算法在之前更难的区域中理论上都会失败。 我们的定理建立了渐近最优恢复界限，这个界限在常数上紧致，并且随着簇/子矩阵数量的增长而成立，同时为多项式时间算法提供了比已知更强的性能保证。 我们的研究表明了统计与计算考虑因素之间的权衡，并表明渐近最优恢复界限可能无法由多项式时间算法实现。 显示英文摘要

摘要： We consider two closely related problems: planted clustering and submatrix localization. The planted clustering problem assumes that a random graph is generated based on some underlying clusters of the nodes; the task is to recover these clusters given the graph. The submatrix localization problem concerns locating hidden submatrices with elevated means inside a large real-valued random matrix. Of particular interest is the setting where the number of clusters/submatrices is allowed to grow unbounded with the problem size. These formulations cover several classical models such as planted clique, planted densest subgraph, planted partition, planted coloring, and stochastic block model, which are widely used for studying community detection and clustering/bi-clustering. For both problems, we show that the space of the model parameters (cluster/submatrix size, cluster density, and submatrix mean) can be partitioned into four disjoint regions corresponding to decreasing statistical and computational complexities: (1) the \emph{impossible} regime, where all algorithms fail; (2) the \emph{hard} regime, where the computationally expensive Maximum Likelihood Estimator (MLE) succeeds; (3) the \emph{easy} regime, where the polynomial-time convexified MLE succeeds; (4) the \emph{simple} regime, where a simple counting/thresholding procedure succeeds. Moreover, we show that each of these algorithms provably fails in the previous harder regimes. Our theorems establish the minimax recovery limit, which are tight up to constants and hold with a growing number of clusters/submatrices, and provide a stronger performance guarantee than previously known for polynomial-time algorithms. Our study demonstrates the tradeoffs between statistical and computational considerations, and suggests that the minimax recovery limit may not be achievable by polynomial-time algorithms.