CRII: CIF: Fundamental Limits of Conditional Stochastic Optimization

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

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.