FoCM 2014 conference

Workshop C6 - Stochastic Computation

December 18, 14:30 ~ 15:00 - Room A12

Multi-Index Monte Carlo: When Sparsity Meets Sampling

Abdul Lateef Haji Ali

King Abdullah University of Science and Technology, Saudi Arabia   -

We present 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 collaborators 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, and which increase the domain of problem parameters for which we achieve the optimal complexity, $\mathcal{O}({\rm TOL}^{-2})$. We propose a systematic construction of optimal sets of indices for MIMC based on properly defined profits that in turn depend on the average cost per sample and the corresponding weak error and variance. Under standard assumptions on the convergence rates of the weak error, variance and work per sample, the optimal index set turns out to be of Total Degree (TD) type. In some cases, using optimal index sets, MIMC achieves a better rate for the computational complexity than does the corresponding rate when using Full Tensor sets. Moreover, we present a simple numerical example that illustrates the method and its computational benefits.

Joint work with Fabio Nobile (École Polytechnique Fédérale de Lausanne, Switzerland) and Raul Tempone (King Abdullah University of Science and Technology, Saudi Arabia).

View abstract PDF