Robust sample average approximation

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

257 citations recorded by the source corpus.

Sample average approximation (SAA) is a widely popular approach to data-driven decision-making under uncertainty. Under mild assumptions, SAA is both tractable and enjoys strong asymptotic performance guarantees. Similar guarantees, however, do not typically hold in finite samples. In this paper, we propose a modification of SAA, which we term Robust SAA, which retains SAA’s tractability and asymptotic properties and, additionally, enjoys strong finite-sample performance guarantees. The key to our method is linking SAA, distributionally robust optimization, and hypothesis testing of goodness-of-fit. Beyond Robust SAA, this connection provides a unified perspective enabling us to characterize the finite sample and asymptotic guarantees of various other data-driven procedures that are based upon distributionally robust optimization. This analysis provides insight into the practical performance of these various methods in real applications. We present examples from inventory management and portfolio allocation, and demonstrate numerically that our approach outperforms other data-driven approaches in these applications.

Subfields: Computational Mechanics, 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 Computational Mechanics

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

Distributionally Robust Optimization: A Review (2019, unknown): “[43] propose a systematic”
Smart "Predict, then Optimize" (2017, background): “The general approach in Bertsimas and Kallus (2014) considers the problem of accurately estimating an unknown optimization objective using machine learning models, speciﬁcally ML models where the predictions can be described as a weighted combination of training samples, e.g., nearest neighbors and…”
Class-Weighted Classification: Trade-offs and Robust Approaches (2020, background): “A variant that has gained traction more recently is distributionally robust optimization (Ben-Tal et al., 2013; Bertsimas et al., 2014; Namkoong and Duchi, 2017).”
Data-driven robust optimization (2013, methodology): “[14] prove that the test which rejects H0 if ∃(a, b) ∈ B ≡ {a ∈ R, b ∈ R : ‖a‖1 + |b| ≤ 1} such that EP0 [(a ũ− b)]− 1 N N ∑”
Bayesian Robust Optimization for Imitation Learning (2020, methodology): “When the posterior distribution over R is continuous, Equation (6) represents the Sample Average Approximation (SAA) method applied to (5), which is used extensively in stochastic programming [56] with known finite-sample properties [9].”