权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

CRII: CIF: Fundamental Limits of Conditional Stochastic Optimization

CRII：CIF：条件随机优化的基本限制

基本信息

批准号：
1755829
负责人：
Niao He
金额：
$ 17.5万
依托单位：
University of Illinois at Urbana-Champaign
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-06-01 至 2021-05-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1755829&HistoricalAwards=false
关键词：
CRII CIF Fundamental Limits Conditional

项目摘要

Decision-making in the presence of randomness has been a fundamental and longstanding challenge in many fields of science and engineering. In the wake of recent breakthroughs in artificial intelligence, there has been a prominent transition of interests and demands from classical (single-stage) stochastic optimization to multi-stage stochastic programming. In contrast to classical stochastic optimization, multi-stage stochastic problems are known to suffer from the curse of dimensionality, for which efficient universal oracle-based algorithms are not readily available. The goal of this research is to build bridges from classical stochastic optimization to multi-stage stochastic problems by developing an understanding of the fundamental limits of an intermediate class of optimization problems - conditional stochastic optimization - in the hopes of closing the algorithmic and theoretical gaps. Because of its specificity (i.e., it involves nonlinear functions of conditional expectations and lacks unbiased stochastic oracles), this class of optimization problems falls beyond the theoretical and practical grasp of the vast majority of state-of-the-art optimization algorithms. The investigator will undertake a systematic study of this subject by (i) establishing new techniques for the design of algorithms adapted to different observation schemes and exploitable structures and (ii) developing sample complexities and non-asymptotic convergence analysis for the proposed algorithms. This research will significantly extend the current scope of stochastic optimization in both theory and applicability. It will also lay the foundation for achieving the long-term goal of bridging to multi-stage decision-making problems and enriching the computational toolbox and theoretical developments for optimization under uncertainty.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.

在随机性存在的情况下进行决策一直是科学和工程的许多领域中的基本和长期挑战。随着人工智能的突破，人们的兴趣和需求从经典的（单阶段）随机优化到多阶段随机规划有了显著的转变。与经典的随机优化相比，多阶段随机问题被称为遭受灾难的维度，有效的通用基于Oracle的算法是不容易获得的。本研究的目标是通过了解中间一类优化问题（条件随机优化）的基本限制，建立从经典随机优化到多阶段随机问题的桥梁，以期缩小算法和理论差距。由于其特殊性（即，它涉及条件期望的非线性函数，并且缺乏无偏随机预言），这类优化问题福尔斯超出了绝大多数现有技术的优化算法的理论和实际掌握。研究者将对这一主题进行系统的研究，方法是：（一）建立新的技术，用于设计适应不同观测方案和可利用结构的算法;（二）为拟议算法开发样本复杂性和非渐近收敛分析。该研究将在理论和应用上大大扩展目前随机优化的范围。它也将为实现多阶段决策问题的长期目标奠定基础，并丰富计算工具箱和不确定性下优化的理论发展。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估而被认为值得支持。