Preprint C1441/2018
Marcus de Mendes Caldas Raymundo Reaiche
Keywords: Stochastic Programming | Monte Carlo sampling | sample average method | sample complexity | risk averse optimization

In this thesis we study sample complexity issues of a Monte Carlo sampling-based approach that is used for approximating general stochastic programming problems. The thesis is divided into two parts.

In the first part of the text, we derive sample complexity estimates for a class of risk averse stochastic programming problems assuming standard regularity conditions. We consider the class of Optimized Certainty Equivalent (OCE) risk measures. We derive estimates either for static or two-stage problems as for dynamic or T-stage problems. Our results extend the ones obtained previously for risk neutral stochastic programming problems in the static and dynamic settings. In particular, we derive exponential rates of convergence of the statistical estimators associated with the approximate problem to their true counterparts. We note that the constants associated with the exponential rate of convergence deteriorate depending of how large is the Lipschitz constant of the problem's risk measure and of the number of stages T. In this case, our results indicate that in the risk averse setting one needs to construct a scenario tree using a relatively larger number of samples than in the risk neutral setting in order to obtain a good approximation for the solution of the original problem.

In the second part of the thesis, we derive a tight lower bound for the sample complexity of a class of risk neutral T-stage stochastic programming problems. An upper bound estimate was derived previously in the literature. Treating the number of stages T as a varying parameter, our result shows that the number of scenarios needed for approximating the true problem with a desirable level of confidence grows more rapidly with respect to T than exponentially. This work was published in [53].