Learning Combinatorial Non-Convex Structures in Data: Statistical Foundations and Computational Methods

学习复杂数据集中的潜在结构是计算科学和数据科学中的一项关键任务。对于计算机视觉、基因组学和社交网络的应用，隐藏的结构通常具有离散性，这使得传统算法无法扩展到现代大型数据集。为了解决这一计算挑战，本研究将引入统计方法来开发新的模型和快速算法，以恢复数据中的离散结构。计算和统计观点的整合不仅会带来理论上的进步，也会带来用于学习任务的统计软件包。此外，该研究的多个组成部分将带来社会效益，例如揭示对在线匿名的威胁和了解社会两极分化。该项目还将为下一代数据科学家提供高质量的培训和研究机会。更具体地说，研究将集中在三种类型的问题：图和形状匹配，图布局问题，和混合模型。所有这些问题的核心是从嘈杂的、不完整的观测中推断出排列。由于排列和其他隐藏结构的组合性质，相关的优化问题在最坏情况下是高度非凸和难以处理的。为了开发有效的算法，本研究将采取平均情况的观点，并采用各种技术，包括谱方法，凸松弛和非凸局部搜索。从理论上讲，提出的问题和算法的基本限制将以统计和计算效率之间的权衡为特征。在实践方面，所有新方法的实现都将开放源代码，用于跨学科应用，如生物网络对齐和计算机视觉中的对象匹配。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Learning latent structures in complex data sets is a crucial task in computational and data-enabled sciences. For applications in computer vision, genomics, and social networks, the hidden structures are often of discrete nature, making traditional algorithms not scalable to modern large data sets. To address this computational challenge, this research will introduce statistical methodologies to develop new models and fast algorithms for recovering discrete structures in data. The integration of computational and statistical perspectives will lead to not only advancement in theory, but also statistical packages for learning tasks. Moreover, multiple components of the research will bring societal benefits such as uncovering threats to online anonymity and understanding social polarization. This project will also provide high-quality training and research opportunities to next-generation data scientists.More specifically, the research will focus on three types of problems: graph and shape matching, graph layout problems, and mixture models. Central to all these problems is the inference of permutations from noisy, incomplete observations. Due to the combinatorial nature of permutations and other hidden structures, the associated optimization problems are highly non-convex and intractable in the worst case. To develop efficient algorithms, this research will take an average-case perspective and employ a variety of techniques including spectral methods, convex relaxations, and non-convex local search. Theoretically, the fundamental limits of the proposed problems and algorithms will be characterized in terms of the trade-off between statistical and computational efficiency. On the practical front, all implementations of new methods will be made open-source for interdisciplinary applications such as alignment of biological networks and object matching in computer vision.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.