Multi-Index Monte Carlo: when sparsity meets sampling by Prof. Raul Tempone

Overview

Abstract

Last year I provided a quick glance into the research of my KAUST Stochastic Numerics group, giving particular emphasis on the activities of my KAUST students. There I also connected our KAUST research and our educational activities, including the Numerical Methods for Stochastic Differential Equations (AMCS 336) and Stochastic Methods for Engineers (AMCS 308) KAUST courses. In particular, I mainly concentrated on our contributions to Multilevel Monte Carlo Methods for the following mathematical models: Partial Differential Equations with random inputs, Ito Stochastic Differential Equations and Pure Jump Processes. This time, I will focus into our newest method: Multi Index Monte Carlo (MIMC). The MIMC method uses a stochastic combination technique to solve the given approximation problem, generalizing the notion of standard MLMC levels into a set of multi indices that should be properly chosen to exploit the available regularity. Indeed, instead of using first-order differences as in standard MLMC, MIMC uses high-order differences to reduce the variance of the hierarchical differences dramatically. This in turn gives a new improved complexity result that increases the domain of the problem parameters for which the method achieves the optimal convergence rate, $\mathcal{O}(\tol^{-2}).$ Using optimal index sets that we determined, MIMC achieves a better rate for the computational complexity does not depend on the dimensionality of the underlying problem, up to logarithmic factors. We present numerical results related to a three dimensional PDE with random coefficients to substantiate some of the derived computational complexity rates. Finally, using the Lindeberg-Feller theorem, we also show the asymptotic normality of the statistical error in the MIMC estimator and justify in this way our error estimate that allows prescribing both the required accuracy and confidence in the final result.

Reference: Abdul-Lateef Haji-Ali, Fabio Nobile, and Raul Tempone. ``Multi-Index Monte Carlo: When Sparsity Meets Sampling.'', arXiv preprint arXiv:1405.3757 (2014) 

Brief Biography

R. Tempone received his Ph.D. in Numerical Analysis at the Royal Institute of Technology in Stockholm, Sweden in 2002. He has been an Associate Professor with KAUST since 2009 and the Director of the Strategic Research Initiative Center for Uncertainty Quantification since April 2012. Before that, he was an Assistant Professor with Mathematics and Scientific Computing at Florida State University, Tallahasee, from 2005 until 2009. From 2003 until 2005 he was an ICES Postdoctoral Fellow at the University of Texas, Austin. He is currently an associate editor for the following journals: SIAM Scientific Computing, BIT Numerical and Mathematics and Computers & Mathematics with Applications. He is interested in the numerical implementation and analysis of adaptive approximations for deterministic and stochastic differential equations. These include, among others, sampling methods like Monte Carlo and Multi Level Monte Carlo and sparse approximations like Stochastic Collocation and Stochastic Galerkin.  He is also interested in Multiscale and Mean Field approximation for prediction and inference, Experimental Design and Model Validation.

Refreshments: Pizza and Soft Drinks available @ 11:45 am