Abstract

• 考慮優(yōu)化問題，目標函數(shù)是期望的形式
• 問題：高維積分很難準確地計算
• 比較兩種基于Monte Carlo采樣的方法，SA(stochastic approximation)和SAA(sample average approximation)
• 一般認為，SAA能夠有效地利用求解問題的特定結(jié)構(gòu)(比如linear)；但是SA是一種粗粒度的梯度方法，在實際中性能較差
• 本文證明，對于一類凸的隨機問題，經(jīng)過適當改變的SA方法能夠達到和SAA近似的性能

Conclusion

• SA的robust版本在理論上和SAA有相似的計算復(fù)雜度（需要的sample size）
• 適當實現(xiàn)的mirror descent SA算法能夠產(chǎn)生和SAA近似的準確率（相同的sample size）
• SA的實現(xiàn)時間和計算時間比SAA短的多（30-40倍）
• 理論和實驗證明，robust mirror descent SA是SAA方法很好的替代者