Validation analysis of mirror descent stochastic approximation method (Q715058)

A basic difficulty for solving stochastic programming problems is that the objective function is given implicitly as the expectation and as such is difficult to compute with high accuracy. A way of solving such problems is to use randomized algorithms based on Monte Carlo sampling. There are two competing approaches of this type: the sampling average approximation (SAA) and the stochastic approximation (SA) methods. An important property of the SAA approach is that it can provide an estimate of the accuracy of an obtained solution by computing upper and lower (confidence) bounds for the optimal value of the true problem. The main goal of the paper is to show that, for a certain class of stochastic convex problems, the mirror descent SA method can also provide similar bounds but with considerably less computational effort.