Abstract
- 考虑优化问题，目标函数是期望的形式
- 问题：高维积分很难准确地计算
- 比较两种基于Monte Carlo采样的方法，SA(stochastic approximation)和SAA(sample average approximation)
- 一般认为，SAA能够有效地利用求解问题的特定结构(比如linear)；但是SA是一种粗粒度的梯度方法，在实际中性能较差
- 本文证明，对于一类凸的随机问题，经过适当改变的SA方法能够达到和SAA近似的性能
Conclusion
- SA的robust版本在理论上和SAA有相似的计算复杂度（需要的sample size）
- 适当实现的mirror descent SA算法能够产生和SAA近似的准确率（相同的sample size）
- SA的实现时间和计算时间比SAA短的多（30-40倍）
- 理论和实验证明，robust mirror descent SA是SAA方法很好的替代者
