Solving Stochastic Optimization via Sample Average Approximation

137 concepts107 papers

Many real-world decision-making problems require optimizing an outcome under intense uncertainty. Whether scheduling electric vehicle charging grids, planning robot trajectories over shifting terrains, or allocating resources during an epidemic, the core mathematical challenge remains the same: minimizing an expected cost function.

$$\min_{x \in X} \mathbb{E}_{\xi} [f(x, \xi)]$$

Here, $x$ represents the decision variables, and $\xi$ is a random variable drawn from a probability distribution representing real-world uncertainty (such as future power demand, physical contact forces, or disease transmission rates).

Computing this expectation exactly is often impossible. If $\xi$ is continuous or high-dimensional, evaluating the expectation requires solving an intractable multi-dimensional integral. If we attempt to optimize this objective using standard stochastic gradient descent (SGD), we are forced to deal with noisy gradient estimates at every step. This leads to slow convergence, highly sensitive step-size tuning, and an inability to use powerful off-the-shelf deterministic optimization algorithms.

Sample Average Approximation (SAA)—also closely related to the scenario approach—is a paradigm that resolves this intractability by transforming a stochastic optimization problem into a deterministic one.


The Core Intuition: The Deterministic Freeze

The fundamental insight behind SAA is simple: replace the true, intractable probability distribution of $\xi$ with an empirical distribution derived from a finite set of $N$ randomly sampled scenarios, $\{\xi^1, \xi^2, \dots, \xi^N\}$.

By doing this, the expected value objective transforms into a simple sample average:

$$\min_{x \in X} \frac{1}{N} \sum_{i=1}^N f(x, \xi^i)$$

While this looks like a straightforward Monte Carlo approximation, the magic lies in how these samples are treated during optimization.

In traditional stochastic approximation (like SGD), new random samples are drawn at every single iteration. The optimization landscape is constantly shifting under the optimizer's feet.

SAA, by contrast, performs a deterministic freeze. It draws a fixed set of "base samples" before the optimization begins and holds them constant throughout the entire optimization process.

By freezing the samples, the objective function ceases to be a noisy, probabilistic simulation. Instead, it becomes a fixed, static, and deterministic surface. This transformation unlocks a massive computational advantage: because the surface is deterministic, we can compute exact gradients and Hessians, allowing us to deploy highly efficient, higher-order deterministic optimizers like quasi-Newton methods (e.g., L-BFGS) or commercial mixed-integer linear programming (MILP) solvers.


Unlocking Powerful Optimizers

The practical power of freezing base samples is vividly illustrated in modern machine learning and Bayesian optimization frameworks.

In BoTorch: A Framework for Efficient Monte-Carlo Bayesian Optimization, Maximilian Balandat et al. demonstrate how SAA makes complex, non-analytic acquisition functions tractable. By fixing a set of base samples, stochastic acquisition functions are converted into smooth, deterministic surfaces. This allows the framework to leverage auto-differentiation and quasi-Newton methods, achieving faster and more reliable convergence than standard stochastic gradient methods. The authors extend this principle in Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization, showing that SAA enables the parallel optimization of multi-objective criteria using fast, higher-order deterministic search methods.

A similar breakthrough occurs in probabilistic inference. In Sample Average Approximation for Black-Box VI, Javier Burroni et al. apply SAA to Black-Box Variational Inference. Traditional variational inference relies heavily on SGD, which requires tedious tuning of learning rate schedules. By fixing the noise samples, the authors transform the stochastic variational objective into a deterministic function, enabling the use of robust deterministic optimization algorithms and automated line search methods that drastically accelerate inference.


SAA Across Diverse Domains

Because SAA reduces probabilistic uncertainty to a finite set of deterministic scenarios, it serves as a mathematical bridge across a wide variety of engineering disciplines.

Robotics and Control

In contact-rich robot manipulation, planners often smooth out discontinuous physics models to make trajectory optimization easier. However, in Is Linear Feedback on Smoothed Dynamics Sufficient for Stabilizing Contact-Rich Plans?, Yuki Shirai et al. utilize SAA to optimize system performance across a distribution of uncertain parameters, ensuring that trajectories remain robust to geometric variations. Similarly, Alexandre Capone et al. in Anticipating the Long-Term Effect of Online Learning in Control use SAA to estimate the expected cost of future control trajectories, bypassing the mathematical intractability of exact integration over Gaussian Processes.

Network Design and Epidemic Control

Managing stochastic processes on massive graphs—such as predicting how an infection spreads—is notoriously difficult. Prathyush Sambaturu demonstrates in Scalable and Memory-Efficient Algorithms for Controlling Networked Epidemic Processes Using Multiplicative Weights Update Method that an ensemble of sampled infection scenarios can transform a stochastic epidemic control problem into a deterministic optimization task, scaling to country-sized networks. In a similar vein, Amy E. Babay et al. in Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks generate multiple deterministic snapshots of a graph through sampling, solving a single linear program that performs well across all simulated scenarios.

Operations and Energy Systems

In industrial manufacturing and energy grids, uncertainty often manifests as fluctuating customer orders or volatile renewable energy generation. In A Sample Average Approximation Approach for Aircraft Product Configuration Optimization with Customer Order Uncertainty, Xinyuan Zhang et al. generate multiple realistic scenarios from historical data to optimize aircraft production configurations, avoiding reliance on potentially inaccurate predefined probability distributions. For energy markets, Chaojie Li et al. show in Integrating Demand Response and Renewable Energy In Wholesale Market how SAA replaces continuous random variables with discrete sample distributions, making complex wholesale electricity market clearing models computationally tractable.


Why It Works: Theoretical Guarantees

If we are only optimizing over a finite subset of samples, how can we be sure the solution will hold up in the real world?

The theoretical foundation of SAA guarantees that as the number of scenarios $N$ increases, the optimal objective value and the optimal solutions of the sampled problem converge asymptotically to their true counterparts.

[True Continuous Distribution] 
       │
       ▼ (Monte Carlo Sampling)
[Finite Set of N Fixed Scenarios] 
       │
       ▼ (Deterministic Freeze)
[Static Optimization Surface] ──► Unlocks: L-BFGS, MILP, Convex Solvers

In Disciplined Convex Stochastic Programming: A New Framework for Stochastic Optimization, Alnur Ali highlights that empirical sampling serves as a highly efficient proxy for continuous distributions, converging rapidly to analytical optima with a relatively small number of samples in practical convex modeling.

Furthermore, the framework has been extended to handle complex data dependencies and non-convex environments:

By substituting continuous expectations with a frozen ensemble of simulated realities, Sample Average Approximation bypasses the curse of dimensionality inherent in stochastic calculus, providing an elegant, scalable, and theoretically sound framework for optimizing under uncertainty.

Key Foundational Work

A stochastic programming approach to scheduling in TAC SCM (2004) — contributed 2 concept elements to this direction.
RoxyBot-06: Stochastic Prediction and Optimization in TAC Travel (2009) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sample_average_approximation_dbefd033,
  title = {sample average approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sample-average-approximation/rdr_dbefd0339ef743a3adbe91b679141687},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_sample_average_approximation_dbefd033_v1,
  title = {sample average approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sample-average-approximation/rdr_dbefd0339ef743a3adbe91b679141687/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}

See something wrong? Report a mistake