Collaborative Research: CIF: Small: Convexification-based Decomposition Methods for Large-Scale Inference in Graphical Models

现代社会中普遍存在的系统可以以产生大量数据的相互关联组件的复杂网络为特征。利用这些数据及时做出推断的能力为解决重大社会问题提供了前所未有的机会。例如，可穿戴技术的进步正在改变个性化医疗保健和健康计划的提供方式。更广泛地说，可穿戴设备自然会在人群中创建传感器网络，这些网络中的数据可以用来检测和/或预防疾病、犯罪或环境危害。利用图形模型可以很自然地完成对这些数据的推断。不幸的是，现有的图形模型技术需要严格的假设，而这些假设在现代应用程序中很少得到满足。该项目的目标是通过开发新的计算方法来解决这些缺点，这些计算方法可以从高维数据中自动推断图形模型的拓扑结构，识别和/或纠正异常值和异常，并同时解决估计问题。此外，拟议的研究将导致定义现代数据科学课程的创新教材，并培养具有离散优化，连续优化和统计界面技能的多样化博士生骨干。具有虚假数据和未知网络拓扑的推理问题可以建模为大规模约束混合整数凸优化问题。为了解决组合约束所带来的挑战，该项目采用了两个关键思想的组合。第一个想法是将问题分解为逐步小的问题，这些问题可以通过利用图形模型中固有的马尔可夫属性以分散和并行的方式解决。第二个思想是组合约束的凸化，以减少或防止问题分解所造成的质量损失。与典型的分解方法（如拉格朗日松弛）不同，该项目将开发基于凸化和Fenchel对偶的新技术。特别是，所得到的方法将同时考虑组合限制和非线性损失函数，最终导致小的或没有对偶间隙。该项目的成功完成将在时空数据推理、可解释预测和因果关系识别方面取得重大进展。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Systems prevalent in modern society can be characterized by complex networks of interconnected components that generate massive amounts of data. The ability to make timely inferences using these data presents unprecedented opportunities to solve major societal problems. For example, advances in wearable technology are transforming the delivery of personalized healthcare and wellness programs. More broadly, wearables naturally create sensor networks over populations and the data from these networks can be harnessed to detect and/or prevent diseases, crimes or environmental hazards. Inference from such data can be naturally accomplished using graphical models. Unfortunately, existing technology for graphical models requires stringent assumptions that are seldom satisfied in modern applications. The goal of this project is to address these shortcomings by developing new computational methods that automatically infer the topology of a graphical model from high-dimensional data, identify and/or correct outliers and anomalies, and solve the estimation problems simultaneously. Furthermore, the proposed research will lead to innovative teaching material defining modern data science curricula and develop a diverse cadre of Ph.D. students with skills at the interface of discrete optimization, continuous optimization, and statistics.Inference problems with spurious data and unknown network topologies can be modeled as large-scale constrained mixed-integer convex optimization problems. To address the challenges posed by the presence of the combinatorial constraints, this project employs a combination of two key ideas. The first idea is to decompose the problem into progressively small problems, that can be solved in a decentralized and parallel fashion, by leveraging the Markov property inherent in graphical models. The second idea is the convexification of the combinatorial constraints, to diminish or prevent altogether the loss in quality from the decomposition of the problem. Unlike typical decomposition methods such as Lagrangian relaxation, which can lead to large duality gaps, this project will develop novel techniques based on convexification and Fenchel duality. In particular, the resulting method will account for the combinatorial restrictions and the nonlinear loss function concurrently, ultimately resulting in small or no duality gaps. The successful completion of the project will lead to significant advances in inference with spatio-temporal data, interpretable prediction, and identification of causal relationships.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.