Sample Complexity of Sample Average Approximation for Conditional Stochastic Optimization
Sample Complexity of Sample Average Approximation for Conditional Stochastic Optimization
复制标题
DOI：
10.1137/19m1284865
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Yifan Hu;Xin Chen;Niao He
中科院分区：
文献类型：
--
作者：
Yifan Hu;Xin Chen;Niao He
在本文中，我们研究了一类随机优化问题，称为\{条件随机优化}（CSO），其形式为$\min_{x \in \mathcal{X}} \EE_{\Xi}f_\Xi\Big（{\EE_{\eta|\Xi}[g_\eta（x，\Xi）]}\Big）$，它有着广泛的应用，包括投资组合选择、强化学习、鲁棒学习、因果推理等。假设来自分布$\PP（\Xi）$和条件分布$\PP（\eta）$的样本可用，|\Xi）$，我们建立了CSO的样本平均近似（SAA）的样本复杂度，在各种结构假设下，如Lipschitz连续性，光滑性和误差界条件.我们发现，总的样本复杂度从$\cO（d/\eps^4）$提高到$\cO（d/\eps^3）$时，假设光滑的外部函数，并进一步提高到$\cO（1/\eps^2）$时，经验函数满足二次增长条件。当$\Xi$和$\eta$相互独立时，我们也建立了一个修改的SAA的样本复杂度.一些数值实验进一步支持我们的理论研究结果。关键词：随机优化，样本平均逼近，大偏差理论
In this paper, we study a class of stochastic optimization problems, referred to as the \emph{Conditional Stochastic Optimization} (CSO), in the form of $\min_{x \in \mathcal{X}} \EE_{\xi}f_\xi\Big({\EE_{\eta|\xi}[g_\eta(x,\xi)]}\Big)$, which finds a wide spectrum of applications including portfolio selection, reinforcement learning, robust learning, causal inference and so on. Assuming availability of samples from the distribution $\PP(\xi)$ and samples from the conditional distribution $\PP(\eta|\xi)$, we establish the sample complexity of the sample average approximation (SAA) for CSO, under a variety of structural assumptions, such as Lipschitz continuity, smoothness, and error bound conditions. We show that the total sample complexity improves from $\cO(d/\eps^4)$ to $\cO(d/\eps^3)$ when assuming smoothness of the outer function, and further to $\cO(1/\eps^2)$ when the empirical function satisfies the quadratic growth condition. We also establish the sample complexity of a modified SAA, when $\xi$ and $\eta$ are independent. Several numerical experiments further support our theoretical findings. Keywords: stochastic optimization, sample average approximation, large deviations theory