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

离散优化是在人工智能、机器人和智能城市等各个领域出现的算法设计中的固有挑战。尽管离散优化问题通常是困难的，但先前的工作表明，许多现实世界的实例满足称为子模块化的自然递减性质。与凸性对连续优化的作用类似，子模块化对算法设计起到了转化作用，从而产生了具有强大理论保证的高效优化方法。尽管取得了这一进展，但现有的方法仍存在已知的局限性，可以从当今技术进步所带来的挑战所激发的重新审查中获益。该项目旨在制定一项研究计划，为复杂、动态环境中的离散和子模块优化奠定基础，解决可扩展性和不确定性的挑战，并在更广泛的环境中促进分布式和顺序学习。该项目是跨学科的，以协同教育计划为特色，结合宾夕法尼亚大学研究生和本科课程的发展，具体目标是确定教育培训中的差距，丰富面向工程师的数据科学教学课程。它还旨在利用现有的公共教育平台，为STEM专业的学生建立进入大学的管道，推进围绕数据科学的公众交流，并传播研究成果。提出的研究计划的总体目标是为(1)随机、不确定、动态发展和对抗性变化的环境中的子模块优化开发新的基础框架；（ii）分布式和多智能体系统；（iii）适应情景，实现数据和观测的顺序选择。该项目寻求在最佳可实现的解决方案质量和各种类型的复杂性（特别是计算、通信和样本复杂性）之间建立基本的权衡，并设计满足这种权衡的算法框架。由此产生的理论和算法将应用于现实世界的场景。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.