Achieving First-Order Statistical Improvements in Data-Driven Optimization

Recent proliferation of data-optimization integration has led to a range of methods that aim to improve the statistical performances of data-driven optimization decisions. However, while many of these methods are motivated intuitively from a robustness or regularization perspective, their resulting statistical benefits are often less clear and, even if available, are argued in a case-by-case fashion. We provide a systematic dissection of data-driven optimization formulations using the view of ``directionally perturbed'' empirical optimization, which demonstrably covers most of the existing formulations. On the negative side, we argue that under mild smoothness conditions, any such formulations can result in at best second-order improvements. On the positive side, we show that in the presence of auxiliary information such as the availability of additional unsupervised data, we can construct a principled methodology, by building connections to the concept of Monte Carlo control variate, to achieve general first-order improvements in terms of solution regret.