A data-driven approach to beating SAA out-of-sample
This addresses the problem of improving out-of-sample optimization guarantees for researchers and practitioners in operations research or machine learning, though it highlights trade-offs that may limit practical application.
The paper introduces Distributionally Optimistic Optimization (DOO) models to guarantee better out-of-sample performance than Sample Average Approximation (SAA), but notes that this comes at the cost of increased sensitivity to model error and reduced robustness, especially with limited data.
While 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 is limited.