Scientific Computation Seminar: Multi Index Monte Carlo: when Sparsity meets Sampling

Dr. Raul Tempone, King Abdullah University of Science and Technology (KAUST).

Description: (joint work with A.-L. Haji-Ali and F. Nobile, KAUST)

We propose and analyze a novel Multi Index Monte Carlo (MIMC) method for weak approximation of stochastic models that are described in terms of differential equations either driven by random measures or with random coefficients. The MIMC method is both a stochastic version of the combination technique introduced by Zenger, Griebel and collaborator and an extension of the Multilevel Monte Carlo (MLMC) method first described by Heinrich and Giles. Inspired by Giles's seminal work, instead of using first-order differences as in MLMC, we use in MIMC high-order mixed differences to  reduce the variance of the hierarchical differences dramatically. This in turn yields  new and improved complexity results, which  are natural generalizations of Giles's MLMC analysis. We motivate the systematic construction of optimal sets of indices for MIMC based on properly defined profits and show the asymptotic normality of the statistical error in the resulting MIMC estimator. Finally, we include numerical experiments involving a partial differential equation posed in three spatial dimensions and with random coefficients to substantiate the analysis and illustrate the corresponding computational savings of MIMC.