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方法很好的替代者