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

学习数据中的组合非凸结构：统计基础和计算方法

• 批准号: 2053333
• 负责人: Cheng Mao
• 金额: $ 20万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-06-01 至 2024-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2053333&HistoricalAwards=false
• 关键词: Learning; Combinatorial; Non; Convex; Structures

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.

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

项目成果

Learning mixtures of permutations: Groups of pairwise comparisons and combinatorial method of moments

学习排列组合：成对比较组和矩组合方法

• DOI: 10.1214/22-aos2185
• 发表时间: 2022
• 期刊: The Annals of Statistics
• 作者: Mao, Cheng;Wu, Yihong
• 通讯作者: Wu, Yihong

Random Graph Matching with Improved Noise Robustness

• 发表时间: 2021-01
• 作者: Cheng Mao;M. Rudelson;K. Tikhomirov

Exact matching of random graphs with constant correlation

• DOI: 10.1007/s00440-022-01184-3
• 发表时间: 2021-10
• 期刊: Probability Theory and Related Fields
• 影响因子: 2
• 作者: Cheng Mao;M. Rudelson;K. Tikhomirov

Spectral Graph Matching and Regularized Quadratic Relaxations I Algorithm and Gaussian Analysis

• DOI: 10.1007/s10208-022-09570-y
• 发表时间: 2022-06
• 期刊: Foundations of Computational Mathematics
• 影响因子: 3
• 作者: Z. Fan;Cheng Mao;Yihong Wu;Jiaming Xu