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

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

摘要： 我们考虑两个密切相关的问题：已植结构聚类和次矩阵定位。 已植结构聚类模型假设图是从某些未知聚类生成的，通过根据节点的聚类成员关系随机放置边来构建；任务是在给定图的情况下恢复这些聚类。 特殊情况包括经典的已植团问题、已植最密子图问题、已植划分问题和已植着色问题。 在次矩阵定位问题（也称为双聚类）中，目标是在一个大的随机矩阵内定位具有较高均值的隐藏次矩阵。 特别感兴趣的是允许聚类/次矩阵的数量随问题规模无界增长的情况。 我们研究了这两个问题的统计学和计算学方面，并证明了以下内容。 模型参数的空间可以被划分为四个互不相交的区域，对应于统计复杂性和计算复杂性的递减：（1）“不可能”区域，在此区域内所有算法都失败；（2）“困难”区域，在此区域内指数时间的最大似然估计（MLE）成功；（3）“简单”区域，在此区域内多项式时间的凸化MLE成功；（4）“容易”区域，在此区域内简单的计数/阈值处理程序成功。 此外，我们表明每个算法在前一个更难的区域中都证明会失败。 我们的定理建立了这两个问题的第一个最小最大恢复结果，且提供了多项式时间算法所能达到的最佳保证。 这些结果展示了统计学和计算学考量之间的权衡。 显示英文摘要

摘要： We consider two closely related problems: planted clustering and submatrix localization. The planted clustering model assumes that a graph is generated from some unknown clusters by randomly placing edges between nodes according to their cluster memberships; the task is to recover the clusters given the graph. Special cases include the classical planted clique, planted densest subgraph, planted partition and planted coloring problems. In the submatrix localization problem, also known as bi-clustering, the goal is to locate hidden submatrices with elevated means inside a large random matrix. Of particular interest is the setting where the number of clusters/submatrices is allowed to grow unbounded with the problem size. We consider both the statistical and computational aspects of these two problems, and prove the following. The space of the model parameters can be partitioned into four disjoint regions corresponding to decreasing statistical and computational complexities: (1) the "impossible" regime, where all algorithms fail; (2) the "hard" regime, where the exponential-time Maximum Likelihood Estimator (MLE) succeeds; (3) the "easy" regime, where the polynomial-time convexified MLE succeeds; (4) the "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 first minimax recovery results for the two problems with unbounded numbers of clusters/submatrices, and provide the best known guarantees achievable by polynomial-time algorithms. These results demonstrate the tradeoffs between statistical and computational considerations.