Wasserstein Distributionally Robust Regret Optimization
This work addresses decision-making under uncertainty for machine learning and optimization practitioners, offering a less conservative alternative to DRO, though it is incremental as it builds on existing Wasserstein DRO frameworks.
The paper tackles the issue of overly conservative solutions in Distributionally Robust Optimization (DRO) by studying Wasserstein Distributionally Robust Regret Optimization (DRRO), showing it coincides with Empirical Risk Minimization under certain conditions and providing efficient algorithms for specific cases, with a convex relaxation that demonstrates strong empirical performance and improved optimality gaps.
Distributionally Robust Optimization (DRO) is a popular framework for decision-making under uncertainty, but its adversarial nature can lead to overly conservative solutions. To address this, we study ex-ante Distributionally Robust Regret Optimization (DRRO), focusing on Wasserstein-based ambiguity sets which are popular due to their links to regularization and machine learning. We provide a systematic analysis of Wasserstein DRRO, paralleling known results for Wasserstein DRO. Under smoothness and regularity conditions, we show that Wasserstein DRRO coincides with Empirical Risk Minimization (ERM) up to first-order terms, and exactly so in convex quadratic settings. We revisit the Wasserstein DRRO newsvendor problem, where the loss is the maximum of two linear functions of demand and decision. Extending [25], we show that the regret can be computed by maximizing two one-dimensional concave functions. For more general loss functions involving the maximum of multiple linear terms in multivariate random variables and decision vectors, we prove that computing the regret and thus also the DRRO policy is NP-hard. We then propose a convex relaxation for these more general Wasserstein DRRO problems and demonstrate its strong empirical performance. Finally, we provide an upper bound on the optimality gap of our relaxation and show it improves over recent alternatives.