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

合作研究：CIF：小型：图模型中大规模推理的基于凸化的分解方法

• 批准号: 2006762
• 负责人: Andres Gomez
• 金额: $ 25万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2023-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006762&HistoricalAwards=false
• 关键词: Collaborative; Research; CIF; Small; Convexification

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.

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

项目成果

Linear-step solvability of some folded concave and singly-parametric sparse optimization problems

• DOI: 10.1007/s10107-021-01766-4
• 发表时间: 2022-01
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: A. Gómez;Ziyu He;J. Pang

A graph-based decomposition method for convex quadratic optimization with indicators

• DOI: 10.1007/s10107-022-01845-0
• 发表时间: 2021-10
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: Peijing Liu;S. Fattahi;Andr'es G'omez;Simge Küçükyavuz

On the convex hull of convex quadratic optimization problems with indicators

• DOI: 10.1007/s10107-023-01982-0
• 发表时间: 2022-01
• 期刊: ArXiv
• 作者: Linchuan Wei;Alper Atamtürk;Andr'es G'omez;Simge Küçükyavuz

Learning Optimal Fair Decision Trees: Trade-offs Between Interpretability, Fairness, and Accuracy

学习最优公平决策树：可解释性、公平性和准确性之间的权衡

• DOI: 10.1145/3600211.3604664
• 发表时间: 2023
• 期刊: ACM
• 作者: Jo, Nathanael;Aghaei, Sina;Benson, Jack;Gomez, Andres;Vayanos, Phebe
• 通讯作者: Vayanos, Phebe

Comparing solution paths of sparse quadratic minimization with a Stieltjes matrix

• DOI: 10.1007/s10107-023-01966-0
• 发表时间: 2023-05
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: Ziyu He;Shaoning Han;A. Gómez;Ying Cui;J. Pang