Error Estimation for SAA Solutions to Compound and Risk-Averse Stochastic Programs

Source abstract

This paper is a study on solutions of the sample average approximation method to solve compound stochastic programs. We derive nonasymptotic upper estimates for probabilities of the approximation errors. The results depend on the sample size and use explicit terms rather than unspecified universal constants. They allow for immediate conclusions about nonasymptotic rates for the optimal solutions. Additionally, the results can be used to construct nonasymptotic confidence regions for solutions of compound stochastic programs. In the special case of classical risk-neutral stochastic programs, we end up with upper estimates of deviation probabilities for M-estimators, and their nonasymptotic rates. Moreover, we may also demonstrate how to apply the results to sample average approximation of risk-averse stochastic programs. In this respect we consider stochastic programs expressed in terms of absolute semideviation risk measures and Average Value at Risk. The investigations are based on concentration inequalities from a recent contribution by the author. The line of reasoning does not rely on pathwise analytical properties of the objectives. In particular, continuity or convexity in the parameter is not imposed in advance as usual in the literature on the sample average approximation method. The main results also apply to objectives with Hölder continuous paths. Moreover, they also work for objectives whose paths are piecewise Hölder continuous, as, for example, in two-stage mixed-integer programs.