On the Impossibility of Statistically Improving Empirical Optimization: A Second Order Stochastic Dominance Perspective

When the underlying probability distribution in a stochastic optimization is observed only through data, various data-driven formulations have been studied to obtain approximate optimal solutions. We show that no such formulations can, in a sense, theoretically improve the statistical quality of the solution obtained from empirical optimization. We argue this by proving that the first order behavior of the optimality gap against the oracle best solution, which includes both the bias and variance, for any data-driven solution second order stochastically dominates that from empirical optimization as long as suitable smoothness holds with respect to the underlying distribution. We demonstrate this impossibility of improvement in examples ranging across regularized optimization, distributionally robust optimization, parametric optimization, and Bayesian generalizations. We also discuss the connections of our results to other perspectives in statistics and data-driven optimization and illustrate practical implications in choosing among data-driven formulations. This paper was accepted by J. George Shanthikumar, data science. Funding: This work was supported by the National Science Foundation Division of Information and Intelligent Systems [Grant 1849280] and Division of Civil, Mechanical, and Manufacturing Innovation [Grant 1834710]. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2024.04482 .