Sample average approximation with sparsity-inducing penalty for high-dimensional stochastic programming
Sample average approximation with sparsity-inducing penalty for high-dimensional stochastic programming
复制标题
DOI：
10.1007/s10107-018-1278-0
复制
发表时间：
2018-05
影响因子：
2.7
通讯作者：
Hongcheng Liu;Xue Wang;Tao Yao;Runze Li;Y. Ye
中科院分区：
文献类型：
--
作者：
Hongcheng Liu;Xue Wang;Tao Yao;Runze Li;Y. Ye
随机规划（SP）的传统样本平均近似（SAA）方案的理论表明，样本数量应该是问题维度数量的多项式，以确保适当的优化精度。在本文中，我们研究了在全局最小化器稀疏或可以通过稀疏解近似的情况下对 SAA 的修改。通过使用称为折叠凹罚分（FCP）的正则化罚分，我们表明，如果局部求解 FCP 正则化 SAA 公式，则在逼近凸 SP 的全局解时所需的样本数量可以显着减少：样本大小仅需要在维数上是多对数。还讨论了 FCP 正则化器对于非凸 SP 的功效。作为我们结果的直接暗示，即使问题维度不能由样本大小的任何多项式函数作为上限，高维统计学习中的一类灵活的折叠凹惩罚稀疏 M 估计器也可能产生良好的性能。
The theory on the traditional sample average approximation (SAA) scheme for stochastic programming (SP) dictates that the number of samples should be polynomial in the number of problem dimensions in order to ensure proper optimization accuracy. In this paper, we study a modification to the SAA in the scenario where the global minimizer is either sparse or can be approximated by a sparse solution. By making use of a regularization penalty referred to as the folded concave penalty (FCP), we show that, if an FCP-regularized SAA formulation is solved locally, then the required number of samples can be significantly reduced in approximating the global solution of a convex SP: the sample size is only required to be poly-logarithmic in the number of dimensions. The efficacy of the FCP regularizer for nonconvex SPs is also discussed. As an immediate implication of our result, a flexible class of folded concave penalized sparse M-estimators in high-dimensional statistical learning may yield a sound performance even when the problem dimension cannot be upper-bounded by any polynomial function of the sample size.