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

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

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.