Multilevel Monte Carlo metamodeling

Approximating the function that maps the input parameters of the simulation model to the expectation of the simulation output is an important and challenging problem in stochastic simulation metamodeling. Because an expectation is an integral, this function approximation problem can be seen as parametric integration - approximating the function that maps a parameter vector to the integral of an integrand that depends on the parameter vector. S. Heinrich and coauthors have proved that the multilevel Monte Carlo (MLMC) method improves the computational complexity of parametric integration, under some conditions. We prove similar results under different conditions that are more applicable to stochastic simulation metamodeling problems in operations research. We also propose a practical MLMC procedure for stochastic simulation metamodeling with user-driven error tolerance. In our simulation experiments, this procedure was up to tens of thousands of times faster than standard Monte Carlo.