Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations

By Peyman Mohajerin Esfahani, D. Kühn. 2015

2,107 citations recorded by the source corpus.

We consider stochastic programs where the distribution of the uncertain parameters is only observable through a finite training dataset. Using the Wasserstein metric, we construct a ball in the space of (multivariate and non-discrete) probability distributions centered at the uniform distribution on the training samples, and we seek decisions that perform best in view of the worst-case distribution within this Wasserstein ball. The state-of-the-art methods for solving the resulting distributionally robust optimization problems rely on global optimization techniques, which quickly become computationally excruciating. In this paper we demonstrate that, under mild assumptions, the distributionally robust optimization problems over Wasserstein balls can in fact be reformulated as finite convex programs—in many interesting cases even as tractable linear programs. Leveraging recent measure concentration results, we also show that their solutions enjoy powerful finite-sample performance guarantees. Our theoretical results are exemplified in mean-risk portfolio optimization as well as uncertainty quantification.

Subfields: Economics and Econometrics, Management Science and Operations Research, Ocean Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

In Management Science and Operations Research

In Ocean Engineering

Citations in the corpus

Certifying Some Distributional Robustness with Principled Adversarial Training (2017, background): “…ﬁnite-dimensional parametrizations for P , such as constraint sets for moments, support, or directional deviations [17, 20, 27], as well as non-parametric distances for probability measures such as f -divergences [5, 6, 40, 44, 21, 47], and Wasserstein distances [23, 59, 9, 24, 10, 25, 37].”
The Cramer Distance as a Solution to Biased Wasserstein Gradients (2017, methodology): “The Wasserstein metric can be applied to distributions with non-overlapping supports, and has good out-of-sample performance (Esfahani and Kuhn, 2015).”
Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization (2019, background): “Prior work in DRO typically deﬁnes the uncertainty set Q as a divergence ball around the training distribution over ( x, y ) (Ben-Tal et al., 2013; Lam & Zhou, 2015; Duchi et al., 2016; Miyato et al., 2018; Esfahani & Kuhn, 2018; Bertsimas et al., 2018; Blanchet & Murthy, 2019).”
Regret in the Newsvendor Model with Demand and Yield Randomness (2021, methodology): “…close to a reference distribution with respect to certain distance measures, among which the most popular are ϕ -divergences (Ben-Tal et al. 2013, Jiang and Guan 2018, Wang et al. 2016) and the Wasserstein distance (Blanchet and Murthy 2019, Gao and Kleywegt 2016, Mohajerin Esfahani and Kuhn 2018).”
Regularization via Mass Transportation (2017, methodology): “Moreover, Theorem 3.6 in [29] implies that if η N converges to 0 at a carefully chosen rate ( e.g. , η N = exp( −√ N )), then the solution of the distributionally robust learning problem (4) with Wasserstein radius ρ = ρ N ( η N ) converges almost surely to the solution of the ideal learning…”
Learning Models with Uniform Performance via Distributionally Robust Optimization (2018, methodology): “This power, however, means that tractable reformulations are only available under restrictive scenarios [81, 38, 87], and they remain computationally challenging.”
Wasserstein Distributional Robustness and Regularization in Statistical Learning (2017, background): “Indeed, such an equivalence has been established in Esfahani and Kuhn (2017) for piecewise-linear convex loss, Shaﬁeezadeh-Abadeh et al. (2015) for logistic regression, and in Blanchet et al. (2016) for linear regression and support vector machines.”
Learning Student Networks with Few Data (2020, background): “(Mohajerin Esfahani and Kuhn 2018, Theorem 6.3) presents an upper bound related to the empirical risk ˆ R .”
Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications (2021, background): “Distri-butionally robust optimization [273] provides a promising way to achieve worst-case probabilistic performance by incorporating all sample-generating distributions into an ambiguity set.”
Evaluating Machine Accuracy on ImageNet (2020, background): “…goal of distributionally robust optimization (DRO) is to ﬁnd models that minimize the worst case expected error over a set of probability distributions (Abadeh et al., 2015; Ben-Tal et al., 2013; Delage & Ye, 2010; Duchi et al., 2019; Esfahani & Kuhn, 2018; Sagawa et al., 2019; Sinha et al., 2017).”
Does Distributionally Robust Supervised Learning Give Robust Classifiers? (2016, background): “DRSL by Esfahani & Kuhn (2015), Blanchet et al. (2016) and Sinha et al. (2017) lets the uncertainty set of test distributions be a Wasserstein ball from the training distribution.”
Optimization under Uncertainty in the Era of Big Data and Deep Learning: When Machine Learning Meets Mathematical Programming (2019, background): “Therefore, various ways of constructing ambiguity sets based on uncertainty data were extensively studied [114, 116, 117].”
BREEDS: Benchmarks for Subpopulation Shift (2020, background): “Distribution shifts that are small with respect to some f -divergence have been studied in prior theoretical work [Ben+13; DGN16; EK18; ND16].”
Recovering Best Statistical Guarantees via the Empirical Divergence-Based Distributionally Robust Optimization (2016, background): “This observation has been pointed out by several authors (e.g., Jiang and Guan (2012), Esfahani and Kuhn (2015)) and forces the use of kernel density estimators to set the baseline.”