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.

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

项目成果

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

一些折叠凹单参数稀疏优化问题的线性步可解性

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

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

基于图的带指标凸二次优化分解方法

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

On the convex hull of convex quadratic optimization problems with indicators

带指标的凸二次优化问题的凸包

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

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

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

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

Ideal formulations for constrained convex optimization problems with indicator variables

带指示变量的约束凸优化问题的理想公式

• DOI: 10.1007/s10107-021-01734-y
• 发表时间: 2020-06-30
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: Linchuan Wei;A. Gómez;Simge Küçükyavuz
• 通讯作者: Simge Küçükyavuz