Optimize-via-Estimate: How to Make Finite-Sample Corrections for Sampling Uncertainty in Data-Driven Optimization

We propose a novel procedure for correcting for the effects of sampling and parameter uncertainty in data-driven convex optimization. We consider the data-driven setting wherein the distribution lies in a parametric family with unknown parameter. The decision-maker possesses a historical data set, from which solves a prescriptive solution as a function mapping such a data set to decisions, and measures its out-of-sample performance as an average over data sets of the same size under the sampling distribution. As the parameter is unknown to the decision-maker, we argue that this problem is ill-defined and further prove that there cannot exist solutions generalizably optimal over all parameters. As such, we formulate the problem as a weighted multi-criteria optimization with weights defined by a density (termed ‘prior’) over the uncertain parameter, and call its optimal solution prior optimal. We prove that sufficient conditions for prior optimality reduces to functions of the sufficient statistic of the parametric family, and this function can be solved as a point-wise optima of a corrected function of the original objective, with terms accounting for parameter uncertainty and sampling uncertainty respectively. The correction for sampling interpretation is verified by a close to (but not) zero ex-ante regret against a perfect information oracle in numerical illustrations on the newsvendor and portfolio optimization problems.