CAREER: Submodular Optimization in Complex Environments: Theory, Algorithms, and Applications

职业：复杂环境中的子模优化：理论、算法和应用

• 批准号: 1943064
• 负责人: Hamed Hassani
• 金额: $ 40万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-06-01 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1943064&HistoricalAwards=false
• 关键词: CAREER; Submodular; Optimization; Complex; Environments

Discrete optimization is an inherent challenge in algorithm design arising in various domains such as artificial intelligence, robotics, and smart cities. Even though discrete optimization problems are hard in general, prior work has shown that many real-world instances satisfy a natural diminishing property called submodularity. Playing an analogous role as convexity does for continuous optimization, submodularity has been transformational for algorithm design, leading to efficient optimization methods with strong theoretical guarantees. Despite this progress, the existing methodologies suffer known limitations and can benefit from a reexamination inspired by the challenges set forth by today's technological advances. This project aims to develop a research plan that builds the foundations of discrete and submodular optimization in complex, dynamic environments, addressing the challenges of scalability and uncertainty, and facilitating distributed and sequential learning in much broader settings. This project is interdisciplinary, featuring a synergistic education plan that incorporates development of both graduate and undergraduate courses at the University of Pennsylvania with the specific goal of identifying gaps in educational training and enriching the curriculum for teaching data science to engineers. It also aims to use available public education platforms to build a pipeline for STEM majors entering college, advance public communication around data science, and disseminate research results.The overarching goal of the proposed research program is to develop novel and foundational frameworks for submodular optimization in (i) stochastic, uncertain, dynamically evolving, and adversarially changing environments; (ii) distributed and multi-agent systems; and (iii) adaptive scenarios enabling sequential selection of data and observations. The project seeks to establish fundamental trade-offs between the best attainable solution quality and various types of complexities (specifically, computation, communication, and sample complexities), and devise algorithmic frameworks that meet such trade-offs. The resultant theory and algorithms will be applied to real-world scenarios.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.

离散优化是在人工智能，机器人和智能城市等各个领域中引起的算法设计中的固有挑战。尽管总体上很难进行离散的优化问题，但先前的工作表明，许多现实世界实例满足了一种自然减少的属性，称为suppodulinity。扮演着连续优化的类似作用，子二次性在算法设计方面已经转化，从而导致具有强大理论保证的有效优化方法。尽管取得了这种进步，但现有的方法论却遭受了已知的局限性，并且可以受益于受到当今技术进步所面临的挑战的启发的重新审查。该项目旨在制定一项研究计划，该计划在复杂的，动态的环境中建立离散和下义优化的基础，以应对可扩展性和不确定性的挑战，并在更广泛的环境中促进分布式和顺序学习。该项目是跨学科的，具有协同的教育计划，该计划纳入了宾夕法尼亚大学的研究生和本科课程的发展，其具体目标是确定教育培训的差距并丰富了向工程师教数据科学的课程。它还旨在使用可用的公共教育平台来建立进入大学的STEM专业的管道，围绕数据科学进行公共交流并传播研究结果。拟议的研究计划的总体目标是在（i）（i）随机，不确定的，动态发展的环境中开发新颖的和基础框架，以进行supportational; （ii）分布式和多代理系统； （iii）自适应场景，可以选择数据和观察结果。该项目旨在在最佳可达到的解决方案质量与各种类型的复杂性（特别是计算，通信和样本复杂性）之间建立基本的权衡，并设计符合此类权衡的算法框架。 最终的理论和算法将应用于现实世界情景。该奖项反映了NSF的法定任务，并使用基金会的知识分子优点和更广泛的影响评估标准，被认为值得通过评估来获得支持。

项目成果

Collaborative Learning of Discrete Distributions under Heterogeneity and Communication Constraints

• 发表时间: 2022-06
• 作者: Xinmeng Huang;Dong-hwan Lee;Edgar Dobriban;Hamed Hassani

Demystifying Disagreement-on-the-Line in High Dimensions

• DOI: 10.48550/arxiv.2301.13371
• 发表时间: 2023-01
• 期刊: ArXiv
• 作者: Dong-Hwan Lee;Behrad Moniri;Xinmeng Huang;Edgar Dobriban;Hamed Hassani