When Can We Cluster Data? Improved Conditions for Perfect Recovery and Numerical Methods

聚类过程在科学和工程中无处不在，特别是在海量数据集和复杂网络的分析中。聚类的目的是将给定的数据集分成相似的组，称为聚类。尽管存在许多聚类的启发式方法（并且被广泛使用），但这种学习任务的理论性质却没有得到很好的理解。相对较少的理论分析已经进行了建立条件下，我们可能期望成功地聚类数据。这个项目的目标是为聚类建立现实的理论保证，无论是在适合聚类的数据方面，还是在开发有效的、计算效率高的算法方面。该项目将通过图像处理、天文学和物理学、数学生物学、社会网络分析和高维统计学的应用来促进跨学科研究。该项目还将通过开发专注于机器学习与大规模优化互动的新课程、跨学科本科研究项目和K-12外展项目，为研究生和本科生提供教育机会。该项目侧重于两个主要的研究重点。第一部分涉及平均情况分析的泛化和聚类模型问题凸松弛的完美恢复的理论保证，例如最密集的子矩阵定位和图划分问题。这些分析的目标是将现有的技术状态扩展到更能代表实际应用中观察到的数据的概率模型。将进行广泛的平均种植案例分析，以建立在随机块模型推广下的完美恢复的计算和信息理论界限。第二个重点将集中在设计、分析和实现大规模半确定和非线性优化的数值方法，特别关注聚类和分类模型问题的算法。通过理论收敛分析和数值仿真来说明该方法的有效性。该项目由计算数学项目和促进竞争研究的既定项目（EPSCoR）共同资助。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The clustering procedure is ubiquitous in science and engineering, especially in analysis of massive data sets and complex networks. The purpose of clustering is to divide a given data set into groups of similar items, called clusters. Although many heuristics for clustering exist (and are widely used), the theoretical properties of this learning task are less well-understood. Relatively few theoretical analyses have been performed establishing conditions under which we may expect to successfully cluster data. The goal of this project is to establish realistic theoretical guarantees for clustering, both in terms of data amenable to clustering as well as in the development of effective, computationally efficient algorithms. The project will facilitate interdisciplinary research via applications in image processing, astronomy and physics, mathematical biology, social network analysis, and high-dimensional statistics. The project will also provide educational opportunities for graduate and undergraduate students through the development of new courses focusing on the interaction of machine learning and large-scale optimization, interdisciplinary undergraduate research programs, and K-12 outreach programs.The project focuses on two main research thrusts. The first concerns the generalization of average case analyses and theoretical guarantees for perfect recovery for convex relaxations of model problems for clustering, such as the densest submatrix localization and graph partition problems. The goal of these analyses is to extend the existing state of the art to probabilistic models for data that are more representative of data observed in practical applications. Extensive average planted case analyses will be performed to establish computational and information-theoretic bounds for perfect recovery under generalizations of the stochastic block model. The second thrust will focus on the design, analysis, and implementation of numerical methods for large-scale semidefinite and nonlinear optimization, with specific focus on the algorithms for model problems for clustering and classification. Theoretical convergence analysis and numerical simulation will be performed to illustrate the efficacy of the methods. This project is jointly funded by the Computational Mathematics program and the Established Program to Stimulate Competitive Research (EPSCoR).This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.