Data-driven robust optimization

By Dimitris J. Bertsimas, Vishal Gupta, Nathan Kallus. 2013

706 citations recorded by the source corpus.

The last decade witnessed an explosion in the availability of data for operations research applications. Motivated by this growing availability, we propose a novel schema for utilizing data to design uncertainty sets for robust optimization using statistical hypothesis tests. The approach is flexible and widely applicable, and robust optimization problems built from our new sets are computationally tractable, both theoretically and practically. Furthermore, optimal solutions to these problems enjoy a strong, finite-sample probabilistic guarantee whenever the constraints and objective function are concave in the uncertainty. We describe concrete procedures for choosing an appropriate set for a given application and applying our approach to multiple uncertain constraints. Computational evidence in portfolio management and queueing confirm that our data-driven sets significantly outperform traditional robust optimization techniques whenever data are available.

Subfields: Management Science and Operations Research, Statistics and Probability

How researchers see this paper

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

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

Certifying Some Distributional Robustness with Principled Adversarial Training (2017, background): “Previous approaches to distributional robustness have considered finite-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]”
Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization (2019, background): “Prior work in DRO typically defines 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).”
Robust sample average approximation (2014, background): “In [7], the authors show how hypothesis tests can be used to construct uncertainty sets for robust optimization problems, and establish a finite-sample guarantee that is similar in spirit to our own.”
Bio-inspired computation: Where we stand and what's next (2019, background): “elaborated on different methodological proposals to build good uncertainty sets, including approaches hinging on the partial availability of data for better adapting them [95,96].”
Towards Out-Of-Distribution Generalization: A Survey (2021, background): “…error over an uncertainty distribution set, so as to protect the model against the potential distributional shifts within the uncertainty set, which is often constrained by moment or support conditions [154], [155], f -divergence [1], [153], [156] and Wasserstein distance [126], [135], [152].”
Certifiable Distributional Robustness with Principled Adversarial Training (2017, background): “…have considered ﬁnite-dimensional parametrizations for P , such as constraint sets for moments, support, or directional deviations [14, 17, 21], as well as non-parametric distances for probability measures such as f -divergences [4, 5, 32, 29, 18, 35], and Wasserstein distances [8, 19, 45].”
Distributionally Robust Neural Networks (2020, background): “Prior work in DRO typically defines the uncertainty set Q as a divergence ball around the training distribution over (x, y) (Ben-Tal et al., 2013; Miyato et al., 2015; Lam & Zhou, 2015; Blanchet & Murthy, 2016; Duchi et al., 2016; Esfahani & Kuhn, 2018; Bertsimas et al., 2018).”
From Predictive to Prescriptive Analytics (2014, background): “Bertsimas et al. (2014)), and datadriven mean-variance distributionally-robust optimization (cf. Delage and Ye (2010), Calafiore and El Ghaoui (2006)). A notable alternative approach to decision making under uncertainty in OR/MS problems is robust optimization (cf. Ben-Tal et al. (2009), Bertsimas e”
A robust optimization approach for dynamic traffic signal control with emission considerations (2012, methodology): “Interested reader is referred to Bandi and Bertismas (2012) and Bertsimas et al. (2014) for some discussions on data-driven calibration of the uncertainty set.”
Optimization under Uncertainty in the Era of Big Data and Deep Learning: When Machine Learning Meets Mathematical Programming (2019, methodology): “Various types of data-driven uncertainty sets were developed for static robust optimization based on statistical hypothesis tests [19], copula [158], and probability density contours [159].”
Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach (2016, methodology): “n by constructing conﬁdence regions based on mean and covariance matrices from the data, and Jiang and Guan [35] expand this line of research to other moment constraints. Bertsimas, Gupta, and Kallus [9, 10] develop uncertainty sets based on various linear and higher-order moment conditions; they al”
Robust empirical optimization is almost the same as mean-variance optimization (2018, positive): “While it has some desirable asymptotic properties, outof-sample performance can be poor when the sample size is not sufficiently large or the statistical assumptions that form the basis of empirical optimization are not valid, and robust (worst-case) empirical optimization has emerged as one approac”
Learning Models with Uniform Performance via Distributionally Robust Optimization (2018, background): “Other work [14, 15, 35, 69, 60, 62] studies a scenario similar to our f -divergence formulation (1).”
Robustness to Spurious Correlations via Human Annotations (2020, background): “…invariance (Peters et al., 2016; Meinshausen & B¨uhlmann, 2015; Rothenh¨ausler et al., 2018), and robust optimization (Ben-Tal et al., 2013; Duchi & Namkoong, 2018; Bertsimas et al., 2018; Lam & Zhou, 2015), few prior works seek to elicit information on the possible shifts in unmeasured variables.”
Smart "Predict, then Optimize" (2017, background): “iyanageandShanthikumar(2005),Chuetal.(2008)),sampleaverage approximation (Kleywegt et al. (2002), Schütz et al. (2009), Bertsimas et al. (2014)), and robust optimization (Bertsimas and Thiele (2006), Bertsimas et al. (2013), Wang et al. (2016)). These approaches typically do not have a clear way of ”
Data-driven Affinely Adjustable Distributionally Robust Unit Commitment (2018, methodology): “Recently, dynamic uncertainty set [29], [37] and data-driven uncertainty set [38] have been proposed to reduce the conservatism of RO.”
Distributionally Robust Optimization: A Review (2019, methodology): “[42] propose to form the ambiguity set of distributions using the confidence set of the unknown distribution via goodness-of-fit tests.”
Wasserstein Distributional Robustness and Regularization in Statistical Learning (2017, methodology): “Recently, the emerging ﬁeld of data-driven distributionally robust stochastic optimization (DRSO) (Goh and Sim 2010, Bertsimas et al. 2013, Wiesemann et al. 2014, Ben-Tal et where M ( P n ) is a set of probability distributions on Z constructed from the empirical distribution P n .”