Marcus de Mendes C. R. Reaiche

In this work we present explicit definitions for the sample complexity associated with the Sample Average Approximation (SAA) Method for instances and classes of multistage stochastic optimization problems. For such, we follow the same notion firstly considered in Kleywegt et al. (2001). We define the complexity for an arbitrary class of problems by considering its … Read more

We derive a \emph{lower bound} for the \emph{sample complexity} of the Sample Average Approximation method for a certain class of multistage stochastic optimization problems. In previous works, \emph{upper bounds} for such problems were derived. We show that the dependence of the \emph{lower bound} with respect to the complexity parameters and the problem’s data are comparable … Read more