CRII: CIF: Fundamental Limits of Conditional Stochastic Optimization

点击翻译按钮获取中文摘要

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.