A Data-Driven Approach to Beating SAA Out of Sample

Whereas solutions of distributionally robust optimization (DRO) problems can sometimes have a higher out-of-sample expected reward than the sample average approximation (SAA), there is no guarantee. In this paper, we introduce a class of distributionally optimistic optimization (DOO) models and show that it is always possible to "beat" SAA out-of-sample if we consider not just worst case (DRO) models but also best case (DOO) ones. We also show, however, that this comes at a cost: optimistic solutions are more sensitive to model error than either worst case or SAA optimizers and, hence, are less robust, and calibrating the worst or best case model to outperform SAA may be difficult when data are limited.