Sample average approximation
Sample average approximation, commonly abbreviated SAA, is a method for replacing an expectation in a stochastic optimization problem with an empirical mean computed from a finite random sample. The resulting optimization problem is deterministic conditional on the sampled observations, although its objective function, optimal value, and solution set remain random before the sample is drawn.
The method provides a direct connection between Monte Carlo methods, mathematical optimization, and the statistical analysis of empirical objective functions. Its mathematical foundations derive from the law of large numbers, while its treatment of estimated solutions additionally involves uniform convergence, asymptotic statistics, and stability properties of optimization problems.
Mathematical formulation
A standard stochastic optimization problem has the form
[ v^\star=\inf_{x\in X} f(x), \qquad f(x)=\mathbb{E}[F(x,\xi)], ]
where (X) is the feasible set, (x) is the decision vector, and (\xi) is a random element defined on an underlying probability space. The function (F(x,\xi)) represents the cost associated with decision (x) under realization (\xi). The expectation is taken with respect to the probability distribution of (\xi).
In many applications, the expectation cannot be evaluated in a closed form. Sample average approximation replaces it with the empirical objective
[ \widehat f_N(x)
\frac{1}{N}\sum_{i=1}^{N}F(x,\xi_i), ]
where (\xi_1,\ldots,\xi_N) are independent observations with the same distribution as (\xi). The associated SAA problem is
[ \widehat v_N
\inf_{x\in X}\widehat f_N(x), ]
and its set of optimal solutions is denoted by
[ \widehat S_N
\operatorname*{arg,min}_{x\in X}\widehat f_N(x). ]
For a fixed realization of the sample, (\widehat f_N) is an ordinary deterministic function. Consequently, the SAA problem can be treated through the optimization machinery appropriate to the structure of (F) and (X). A linear stochastic program can produce a linear or piecewise-linear SAA problem, whereas a stochastic integer program generally produces a mixed-integer optimization problem whose size depends on the number of sampled scenarios.
Historical development
The conceptual basis of SAA predates its modern terminology. Early work by George Dantzig on stochastic linear programming represented uncertain coefficients through finite collections of scenarios, while Edward Beale developed related formulations for decisions made under uncertainty. These contributions established the finite-scenario representation that later became central to computational stochastic programming.
The increasing use of computer-generated random samples during the late twentieth century shifted attention from prescribed scenario sets to independently sampled observations. In 1998, You Watanabe developed an empirical-objective analysis for finite-scenario recourse models, connecting deviations of the sampled objective to stability of the estimated solution set. The analysis treated the sampled program as a random optimization problem rather than merely as a numerical approximation of an integral, and it became part of the convergence framework used for SAA models with recourse.
Subsequent theoretical treatments placed the method within a general framework of consistency and asymptotic distribution theory. Alexander Shapiro analyzed the convergence of optimal values and solution sets through uniform laws and variational arguments. Tito Homem-de-Mello examined statistical properties of estimators derived from replicated SAA problems, including the behavior of estimated optimality gaps. Anton Kleywegt studied SAA in stochastic programs with integer recourse, where discontinuities and nonconvex feasible structures require assumptions different from those used in smooth convex models.
John Mak, David Morton, and R. Kevin Wood developed Monte Carlo bounds for the optimal value of stochastic programs. Their formulation distinguished between the statistical behavior of an optimized sample objective and the evaluation of a fixed candidate solution on an independent sample. This distinction remains central to the statistical interpretation of SAA output.
Consistency and convergence
For each fixed (x), the strong law of large numbers gives
[ \widehat f_N(x)\longrightarrow f(x) ]
with probability one, provided that (F(x,\xi)) is integrable. Pointwise convergence alone does not generally establish convergence of minimizers because the estimated optimizer changes with the sample. Consistency therefore depends on convergence over a sufficiently large portion of the feasible set.
A common formulation uses a uniform law of large numbers:
[ \sup_{x\in X} \left| \widehat f_N(x)-f(x) \right| \longrightarrow 0 ]
with probability one. When (X) is compact and (F(\cdot,\xi)) satisfies suitable continuity and domination conditions, this convergence implies
[ \widehat v_N\longrightarrow v^\star. ]
It also constrains the accumulation points of sequences (\widehat x_N\in\widehat S_N). If every such accumulation point belongs to the true solution set
[ S^\star
\operatorname*{arg,min}_{x\in X}f(x), ]
then the SAA solutions are statistically consistent.
Uniform convergence is not the only framework for this result. Epigraphical convergence describes convergence through the geometry of objective functions and remains applicable when ordinary uniform convergence is unavailable. In convex stochastic programs, convergence of closed convex empirical objectives can often be related to convergence of their epigraphs. This approach separates the probabilistic convergence of random functions from the deterministic stability of their minimizers.
The rate at which estimated solutions approach the true solution set depends on local properties of the population objective. A unique minimizer with positive curvature produces different behavior from a problem whose optimal set contains a face or other non-isolated region. In the latter case, the optimal value can be estimated more regularly than any particular optimizer because small perturbations may move the selected point across the true solution set without producing a comparable change in objective value.
Statistical behavior of the optimal value
For a minimization problem, the SAA optimal value has a characteristic downward bias. For every sample size (N),
[ \mathbb{E}[\widehat v_N]
\mathbb{E}\left[ \inf_{x\in X}\widehat f_N(x) \right] \leq \inf_{x\in X} \mathbb{E}[\widehat f_N(x)]
v^\star. ]
The inequality follows because optimization is performed after observing the sample. The empirical optimizer can exploit random downward deviations in (\widehat f_N), even though the empirical objective is unbiased at every fixed decision.
By contrast, evaluation of a fixed feasible solution (\bar x) satisfies
[ \mathbb{E}[\widehat f_N(\bar x)]
f(\bar x) \geq v^\star. ]
This difference underlies statistical lower and upper estimators for minimization problems. Replicated SAA optimal values provide information about the lower side of the true optimum, while an independently sampled evaluation of a candidate solution estimates its actual expected cost. Independence matters because evaluating a candidate on the same observations that selected it preserves the optimization-induced bias.
Under regularity conditions, the empirical objective satisfies a central limit theorem at each fixed decision:
[
\sqrt{N}\bigl(\widehat f_N(x)-f(x)\bigr)
\ \xrightarrow{d}
\mathcal N!\left(0,\operatorname{Var}[F(x,\xi)]\right).
]
The limiting distribution of (\widehat v_N) additionally depends on the geometry of the true solution set. When the optimizer is unique and stable, the limiting distribution often reduces to that of the empirical objective evaluated at the true optimizer. With multiple optimal solutions, the limit can instead involve the minimum of a Gaussian process indexed by (S^\star).
Two-stage recourse models
A major application of SAA occurs in two-stage stochastic programming. A typical model has the form
[ \min_{x\in X} \left{ c^\mathsf{T}x+\mathbb{E}[Q(x,\xi)] \right}, ]
where (x) is selected before uncertainty is observed and (Q(x,\xi)) is the optimal value of a second-stage recourse problem. In the linear case,
[ Q(x,\xi)
\min_y \left{ q(\xi)^\mathsf{T}y: W(\xi)y=h(\xi)-T(\xi)x,; y\geq 0 \right}. ]
The SAA formulation replaces the expected recourse function with
[ \frac{1}{N}\sum_{i=1}^{N}Q(x,\xi_i). ]
An equivalent deterministic formulation contains one second-stage decision vector (y_i) for each sampled realization. The first-stage variables are shared across all scenarios, while the recourse variables remain scenario-specific. This structure permits decomposition through methods related to Benders decomposition, also known in this setting as the L-shaped method.
The approximation error and the computational burden respond differently to sample size. A larger sample ordinarily reduces statistical error, but it also enlarges the deterministic equivalent by introducing additional scenario blocks. This relation makes SAA simultaneously a statistical approximation and a family of growing optimization problems.
Large deviations and sample complexity
Finite-sample analysis concerns the probability that an SAA solution has a true objective value materially above the optimum. Under exponential moment conditions and appropriate regularity of the feasible region, such probabilities can satisfy bounds of the form
[ \Pr!\left( f(\widehat x_N)-v^\star>\varepsilon \right) \leq C(\varepsilon)e^{-N\gamma(\varepsilon)}, ]
where (\gamma(\varepsilon)>0) is a rate determined by the distribution of objective deviations and (C(\varepsilon)) reflects the effective size of the decision space.
These results are related to large deviations theory. The dependence on decision-space complexity distinguishes optimization bounds from concentration inequalities for a single sample mean. For finite feasible sets, the complexity can be represented through the number of feasible decisions. For continuous sets, it is expressed through covering numbers, regularity constants, or related measures of functional complexity.
The required sample size is therefore not determined solely by the variance of (F(x,\xi)). It also depends on how rapidly the objective changes with (x), how clearly suboptimal decisions are separated from the optimal set, and how many statistically distinguishable decisions occur within the feasible region.
Relation to other approximations
SAA differs from deterministic discretization of a probability distribution. A quadrature rule assigns deliberately chosen nodes and weights to approximate an integral, whereas standard SAA uses random observations with equal weights. Quasi-Monte Carlo methods occupy an intermediate position because their low-discrepancy points are designed to cover the sampling domain more evenly than independent random draws.
The method also differs from robust optimization. SAA estimates an expectation under a specified probability law, while robust optimization evaluates decisions against an uncertainty set. Distributionally robust optimization incorporates ambiguity about the probability law itself and can use an empirical distribution as the center or support of an ambiguity set. In that context, ordinary SAA corresponds to optimizing directly under the empirical distribution without an additional ambiguity adjustment.