Robust Stochastic Approximation Approach to Stochastic Programming

TLDR

Stochastic optimization problems involve expectations that are difficult to compute accurately, and although both stochastic approximation (SA) and sample average approximation (SAA) methods have a long history, the prevailing view is that SAA exploits problem structure while SA is a crude subgradient method that often performs poorly. This paper compares SA and SAA Monte Carlo methods and aims to show that a suitably modified SA approach can be competitive and even significantly outperform SAA for certain convex stochastic problems. The authors extend the analysis to convex‑concave stochastic saddle point problems and conduct numerical experiments to evaluate the methods. Numerical experiments show encouraging results, suggesting the modified SA approach can outperform SAA.

Abstract

In this paper we consider optimization problems where the objective function is given in a form of the expectation. A basic difficulty of solving such stochastic optimization problems is that the involved multidimensional integrals (expectations) cannot be computed with high accuracy. The aim of this paper is to compare two computational approaches based on Monte Carlo sampling techniques, namely, the stochastic approximation (SA) and the sample average approximation (SAA) methods. Both approaches, the SA and SAA methods, have a long history. Current opinion is that the SAA method can efficiently use a specific (say, linear) structure of the considered problem, while the SA approach is a crude subgradient method, which often performs poorly in practice. We intend to demonstrate that a properly modified SA approach can be competitive and even significantly outperform the SAA method for a certain class of convex stochastic problems. We extend the analysis to the case of convex-concave stochastic saddle point problems and present (in our opinion highly encouraging) results of numerical experiments.