Sample Average Approximation

333. Sample Average Approximation

Sample Average Approximation (SAA) — replace an intractable expectation in a stochastic program with a Monte Carlo average over scenarios.

333.1. Problem

Original stochastic program:

𝑧^{*} = min_{𝑥} 𝑓 (𝑥) + 𝐸_{𝜉} [𝑄 (𝑥, 𝜉)]

The expectation is hard (high-dimensional integral; complex distribution).

333.2. SAA approximation

Generate $𝑁$ i.i.d. samples $𝜉^{1}, \dots, 𝜉^{𝑁}$ from the distribution of $𝜉$ . Solve:

{\hat{𝑧}}_{𝑁} = min_{𝑥} 𝑓 (𝑥) + \frac{1}{𝑁} \sum_{𝑠 = 1}^{𝑁} 𝑄 (𝑥, 𝜉^{𝑠})

This is just a deterministic mathematical program — with $𝑁$ scenarios. Solvable by standard tools (simplex, branch-and-bound, etc.).

333.3. Convergence

As $𝑁 \to \infty$ :

{\hat{𝑧}}_{𝑁} \to 𝑧^{*} (strong law of large numbers)

with the optimal solution ${\hat{𝑥}}_{𝑁}$ also converging to the true optimum $𝑥^{*}$ . Rate: $𝑂 (\frac{1}{\sqrt{𝑁}})$ by CLT — the error variance decays as $\frac{1}{𝑁}$ , standard error as $\frac{1}{\sqrt{𝑁}}$ .

333.4. Confidence intervals

The objective value ${\hat{𝑧}}_{𝑁}$ from a single SAA run is a random estimate. Standard confidence interval:

CI = [{\hat{𝑧}}_{𝑁} - 1.96 \frac{𝜎_{𝑁}}{\sqrt{𝑁}}, {\hat{𝑧}}_{𝑁} + 1.96 \frac{𝜎_{𝑁}}{\sqrt{𝑁}}]

where $𝜎_{𝑁}$ is the sample standard deviation of the recourse values $𝑄 ({\hat{𝑥}}_{𝑁}, 𝜉^{𝑠})$ .

333.5. Practical SAA algorithm

Generate $𝑁$ samples
Solve SAA problem → ${\hat{𝑥}}_{𝑁}$
Independently evaluate ${\hat{𝑥}}_{𝑁}$ on $𝑀$ fresh samples (out-of-sample, $𝑀 ≫ 𝑁$ ) to estimate true $𝑓 ({\hat{𝑥}}_{𝑁}) + 𝐸 [𝑄 ({\hat{𝑥}}_{𝑁}, 𝜉)]$
Compare in-sample ${\hat{𝑧}}_{𝑁}$ vs out-of-sample estimate. If similar, ${\hat{𝑥}}_{𝑁}$ is a good solution. If much worse out-of-sample, increase $𝑁$ .

This out-of-sample validation is essential — in-sample optimization can over-fit to the scenarios used.

333.6. Choosing $𝑁$

Trade-off:

Larger $𝑁$ : better approximation, but exploding problem size (number of recourse variables = $| 𝑦 | \cdot 𝑁$ )
Smaller $𝑁$ : faster solve, more sample error

Heuristics:

Replication: solve SAA with several smaller $𝑁$ ’s, take the best. Cheaper than one huge $𝑁$ .
Adaptive sampling: start small, grow $𝑁$ until confidence interval is tight enough
Stratified sampling: sample more from high-impact regions of the distribution to reduce variance

333.7. Variance reduction

Plain Monte Carlo has variance $\frac{𝜎^{2}}{𝑁}$ . Tricks to do better:

Antithetic variates — use $𝜉$ and $- 𝜉$ together
Importance sampling — sample more from rare-but-impactful scenarios
Common random numbers — across optimization iterations
Quasi-Monte Carlo (Halton, Sobol sequences) — $𝑂 (\frac{1}{𝑁})$ convergence instead of $𝑂 (\frac{1}{\sqrt{𝑁}})$ for smooth integrands

333.8. When SAA shines

Continuous distributions of $𝜉$ (chance-constrained SP can be cumbersome)
Distributions without closed-form moments
Black-box simulators — easy to sample, hard to integrate analytically