Optimal Allocations for Sample Average Approximation

2018/11/17 by Jaiswal, Prateek, Honnappa, Harsha, Pasupathy, Raghu
#Computation (stat.CO) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1811.07186

Abstract

We consider a single stage stochastic program without recourse with a strictly convex loss function. We assume a compact decision space and grid it with a finite set of points. In addition, we assume that the decision maker can generate samples of the stochastic variable independently at each grid point and form a sample average approximation (SAA) of the stochastic program. Our objective in this paper is to characterize an asymptotically optimal linear sample allocation rule, given a fixed sampling budget, which maximizes the decay rate of probability of making false decision.

Related

• Sample Average Approximation for Stochastic Programming with Equality Constraints
• On Feasibility of Sample Average Approximation Solutions
• First order asymptotics of the sample average approximation method to\n solve risk averse stochastic progams
• Nonasymptotic upper estimates for errors of the sample average approximation method to solve risk averse stochastic programs
• Validating Sample Average Approximation Solutions with Negatively Dependent Batches