The Sample Average Approximation Method for Stochastic Discrete Optimization

By Anton J. Kleywegt, Alexander Shapiro, Tito Homem-de-Mello. 2002

2,003 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Industrial and Manufacturing Engineering, Mathematical Optimization

How researchers see this paper

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

In Computer Networks and Communications

In Industrial and Manufacturing Engineering

In Mathematical Optimization

Citations in the corpus

Predicting Tactical Solutions to Operational Planning Problems under Imperfect Information (2018, background): “Hence, the distance between the SAA solution(s) to (9) and the solution(s) to (7) is shown to converge strongly to zero with respect to N (Kleywegt et al., 2002).”
Recovering Best Statistical Guarantees via the Empirical Divergence-Based Distributionally Robust Optimization (2016, background): “To deﬁne what “best” means, we start by discussing arguably the most natural attempt for handling (1), namely the sample average approximation (SAA) (Shapiro et al. (2014), Wang and Ahmed (2008), Kleywegt et al. (2002)).”
Sample size selection in optimization methods for machine learning (2012, background): “[20] and Shapiro and Homem-de-Mello [29] provide results that show convergence for specific classes of problems.”
The empirical behavior of sampling methods for stochastic programming (2006, background): “In this section, we review a theory, developed recently in [32,17,34], concerning the rate of convergence of the solutions x̂N of the SAA problem (6) to the optimal solution set of the original problem (1).”
Robust Stochastic Approximation Approach to Stochastic Programming (2008, methodology): “Recent theoretical studies (cf. [ 11, 25, 26]) and numerical experiments (see, e.g., [12, 13, 29]) show that the SAA method coupled with a good (deterministic) algorithm could be reasonably eﬃcient for solving certain classes of two-stage stochastic programming problems.”
Smart "Predict, then Optimize" (2017, neutral): “…near-optimal solutions from data include operational statistics (Liyanage and Shanthikumar (2005), Chu et al. (2008)), sample average approximation (Kleywegt et al. (2002), Schütz et al. (2009), Bertsimas et al. (2014)), and robust optimization (Bertsimas and Thiele (2006), Bertsimas et al.…”
BoTorch: Programmable Bayesian Optimization in PyTorch (2019, background): “[51] Anton J Kleywegt, Alexander Shapiro, and Tito Homem-de Mello.”
Stochastic Approximation approach to Stochastic Programming (2013, neutral): “, [6, 16, 17]) and numerical experiments (see, e.”
The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study (2003, methodology): “Kleywegt, Shapiro, and Homem-de-Mello [16] analyzed the behavior of the SAA method when applied to stochastic discrete optimization problems .”
On Complexity of Stochastic Programming Problems (2005, neutral): “guarantees that probability of the event {Ŝδ N ⊂ Sε} is at least 1 − α (see [21],[41, section 3.”
Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework (2012, background): “, [18, 36]) and even significantly outperform it for solving a class of stochastic programming problems.”