Regularized sample average approximation for high-dimensional stochastic optimization under low-rankness
Regularized sample average approximation for high-dimensional stochastic optimization under low-rankness
复制标题
DOI：
10.1007/s10898-022-01206-3
复制
发表时间：
2019-04
影响因子：
1.8
通讯作者：
H. Lee;Charles Hernandez;Hongcheng Liu
中科院分区：
文献类型：
--
作者：
H. Lee;Charles Hernandez;Hongcheng Liu
本文研究了一个具有矩阵变元的期望费用函数最小化的高维随机规划问题。对于这个问题，最广泛应用的解决方案范例之一是样本平均近似（SAA），它使用采样场景的平均成本作为替代来近似期望成本。传统的SAA理论要求当问题维数增加时，样本容量迅速增长。实际上，对于在ap-by-p矩阵上优化的问题，SAA的样本复杂度由给出，以实现一个次优间隙，对于一些多对数函数和一些与维数p和样本大小无关的量。相比之下，本文考虑了正则化SAA（RSAA）与低秩诱导惩罚。我们证明，当SP的最优解是低秩的，RSAA的样本复杂度是，这几乎是线性的，因此表明一个显着较低的依赖于维数。因此，RSAA可以比SAA更有利，特别是对于更大规模和更高维的问题。由于随机规划和统计学习之间的密切对应关系，我们的研究结果还表明，高维低秩矩阵恢复是可能的，一般超出线性模型，即使限制强凸性的常见假设是完全不存在的。
This paper concerns a high-dimensional stochastic programming (SP) problem of minimizing a function of expected cost with a matrix argument. To this problem, one of the most widely applied solution paradigms is the sample average approximation (SAA), which uses the average cost over sampled scenarios as a surrogate to approximate the expected cost. Traditional SAA theories require the sample size to grow rapidly when the problem dimensionality increases. Indeed, for a problem of optimizing over ap-by-pmatrix, the sample complexity of the SAA is given byto achieve an-suboptimality gap, for some poly-logarithmic functionand some quantityindependent of dimensionalitypand sample sizen. In contrast, this paper considers a regularized SAA (RSAA) with a low-rankness-inducing penalty. We demonstrate that, when the optimal solution to the SP is of low rank, the sample complexity of RSAA is, which is almost linear inpand thus indicates a substantially lower dependence on dimensionality. Therefore, RSAA can be more advantageous than SAA especially for larger scale and higher dimensional problems. Due to the close correspondence between stochastic programming and statistical learning, our results also indicate that high-dimensional low-rank matrix recovery is possible generally beyond a linear model, even if the common assumption of restricted strong convexity is completely absent.