Sample Average Approximation

Sample average approximation replaces an intractable expectation with an average over sampled scenarios, converting a stochastic program into a solvable one.

Approximating the expectation

Stochastic programs minimize an expected cost E[F(x, xi)] over a random variable xi, but the expectation is often an integral with no closed form. Sample average approximation (SAA) draws N independent samples xi_1, ..., xi_N and replaces the expectation with the empirical average (1/N) sum F(x, xi_i). The resulting problem is deterministic and can be solved by ordinary methods.

Statistical guarantees

SAA is not a heuristic; it comes with theory. As the sample size N grows, the optimal value and optimal solutions of the SAA problem converge to those of the true stochastic program, and under mild conditions the convergence is at the usual statistical rate. Independent replications with different samples yield confidence intervals on the true optimal value, so the sampling error can be quantified rather than guessed.

• Consistency: SAA optima converge to true optima as N grows
• Confidence bounds: multiple replications bracket the true value
• Gap estimation: compare a candidate solution against a lower-bound estimate
• Variance reduction: common random numbers and importance sampling sharpen estimates

import numpy as np

def saa_objective(x, sampler, N, F):
    xis = sampler(N)                       # draw N scenarios
    return np.mean([F(x, xi) for xi in xis])  # empirical expectation

# optimize saa_objective(., sampler, N, F) over x with any solver,
# then re-estimate the objective on a fresh, larger sample.

Choosing the sample size

A larger N gives a more faithful approximation but a bigger optimization problem, so N trades accuracy for cost. A common workflow solves several small-sample SAA problems to generate candidate solutions cheaply, then evaluates each candidate on a large independent sample to pick the best and estimate its true value with a tight confidence interval. This separates the noisy optimization step from a precise evaluation step.

Role

SAA is the bridge from a stochastic model to a solvable one whenever the underlying distribution can be sampled, including complex, correlated, or simulation-defined distributions with no analytic form. It underpins much of practical stochastic optimization and connects directly to the sample-based objectives used throughout machine learning.