CAREER: Stochastic Nested Composition Optimization: Theory and Algorithms

职业：随机嵌套组合优化：理论和算法

• 批准号: 1653435
• 负责人: Mengdi Wang
• 金额: $ 50万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-02-01 至 2023-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1653435&HistoricalAwards=false
• 关键词: CAREER; Stochastic; Nested; Composition; Optimization

The objective of this Faculty Early Career Development (CAREER) award is to develop foundational theory and efficient computational tools for an important class of data-driven stochastic optimization problems, stochastic nested composition optimization. These nested composition problems arise in many areas such as risk management, machine learning, and online decision making, and are not amenable to classical methods of stochastic optimization. On the theory and methodology side, the project will advance both optimization and data analytics. On the education side, the project will result in curricular innovation that integrates optimization and data analytics in a unified way and offers new case studies on practical applications. The project will promote underrepresented minority students by involving them in frontier research. The research will produce new algorithms and analysis tools that will be useful for many data-intensive applications. These methods will be empirically tested in a collaborative project with a local healthcare system, with the goal of improving healthcare delivery by reducing cost and improving quality of service. Stochastic nested composition optimization constitutes a new class of stochastic optimization problems that involve nested nonlinear composition of multiple expectations and multi-level random variables. This project will (a) establish the basic complexity theory for two-level and multi-level stochastic nested composition optimization and their generalizations; (b) develop efficient algorithms that process streaming data with theoretical guarantees; (c) investigate several special cases of the problem and apply the results to modeling and optimizing healthcare decisions based on real clinical data (obtained through the collaboration with a NJ-based hospital chain); and (d) develop innovative curricula and research projects that can bring students at various levels to frontier technology. The nested composition provides a rich modeling tool for applications that require data-driven decision-making and optimization under uncertainty. A critical challenge is that the objective is no longer a linear functional of the data distribution, and thus existing theory and methods are inappropriate. The nonlinearity with respect to the distribution of data makes the problem fundamentally more difficult than most of the classical problems. Overcoming the analytical challenge calls for an integration of mathematical programming and stochastic analysis. If successful, the research will make a substantial contribution by expanding the scope of stochastic optimization. Theoretically, it will strengthen our mathematical understanding of stochastic optimization and establish foundational sample complexity bounds. Methodologically, it will provide new algorithms and analysis tools for several important problems in data-driven optimization and online learning. The results will establish important connections among several areas in mathematical programming, statistics, and machine learning.

这个教师早期职业发展（CAREER）奖的目标是为一类重要的数据驱动随机优化问题，随机嵌套组合优化开发基础理论和有效的计算工具。这些嵌套组合问题出现在许多领域，如风险管理，机器学习和在线决策，并不适合随机优化的经典方法。在理论和方法方面，该项目将推进优化和数据分析。在教育方面，该项目将导致课程创新，以统一的方式整合优化和数据分析，并提供有关实际应用的新案例研究。该项目将促进代表性不足的少数民族学生参与前沿研究。这项研究将产生新的算法和分析工具，对许多数据密集型应用程序有用。 这些方法将在与当地医疗保健系统的合作项目中进行经验测试，目标是通过降低成本和提高服务质量来改善医疗保健服务。随机嵌套复合优化是一类新的随机优化问题，涉及多个期望和多水平随机变量的嵌套非线性复合。本计画将（a）建立二层与多层随机巢式组合最佳化的基本复杂性理论及其推广：（B）发展有理论保证的处理串流资料的有效演算法;（c）研究该问题的几种特殊情况，并将结果应用于基于真实的临床数据的建模和优化保健决策（d）开发创新课程和研究项目，使不同层次的学生接触前沿技术。嵌套组合为需要在不确定性下进行数据驱动决策和优化的应用程序提供了丰富的建模工具。一个关键的挑战是，目标不再是数据分布的线性函数，因此现有的理论和方法是不合适的。相对于数据分布的非线性使得问题从根本上比大多数经典问题更困难。克服分析的挑战，要求数学规划和随机分析的整合。如果成功，该研究将通过扩大随机优化的范围做出实质性贡献。从理论上讲，它将加强我们对随机优化的数学理解，并建立基本的样本复杂性界限。在方法上，它将为数据驱动优化和在线学习中的几个重要问题提供新的算法和分析工具。研究结果将在数学规划、统计学和机器学习的几个领域之间建立重要的联系。

项目成果

A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization

• DOI: 10.1137/18m1230542
• 发表时间: 2018-12
• 期刊: SIAM J. Optim.
• 作者: Saeed Ghadimi;A. Ruszczynski;Mengdi Wang

Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient

提高随机成分方差的样本复杂性并减少梯度

• DOI: 10.23919/acc45564.2020.9147515
• 发表时间: 2020
• 期刊: American Control Conference
• 作者: Lin, Tianyi;Fan, Chengyou;Wang, Mengdi;Jordan, Michael I.
• 通讯作者: Jordan, Michael I.

Decentralized Gossip Stochastic Bilevel Optimization over Communication Networks

通信网络上的去中心化八卦随机双层优化

• 发表时间: 2022
• 期刊: Advances in neural information processing systems
• 作者: Shuoguang Yang;Xuezhou Zhang;Mengdi Wang
• 通讯作者: Mengdi Wang

Multilevel Stochastic Gradient Methods for Nested Composition Optimization

• DOI: 10.1137/18m1164846
• 发表时间: 2018-01
• 期刊: SIAM J. Optim.
• 作者: Shuoguang Yang;Mengdi Wang;Ethan X. Fang

Accelerating Stochastic Composition Optimization

• 发表时间: 2016-07
• 期刊: J. Mach. Learn. Res.
• 作者: Mengdi Wang;Ji Liu;Ethan X. Fang