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

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

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.