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

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