On Monte Carlo, Multilevel Monte Carlo and Adaptive Multilevel Monte Carlo

Raúl Tempone
King Abdullah University of Science and Technology (KAUST)

We will first recall, for a general audience, the use of Monte Carlo and Multi-level Monte Carlo methods in the context of Uncertainty Quantification. Then we will discuss the recently developed Adaptive Multilevel Monte Carlo (MLMC) Methods for (i) Itô Stochastic Differential Equations, (ii) Stochastic Reaction Networks modeled by Pure Jump Markov Processes and (iii) Partial Differential Equations with random inputs. In this context, the notion of adaptivity includes several aspects such as mesh refinements based on either a priori or a posteriori error estimates, the local choice of different time stepping methods and the selection of the total number of levels and the number of samples at different levels. Our Adaptive MLMC estimator uses a hierarchy of adaptively refined, non-uniform time discretizations, and, as such, it may be considered a generalization of the uniform discretization MLMC method introduced independently by M. Giles and S. Heinrich. In particular, we show that our adaptive MLMC algorithms are asymptotically accurate and have the correct complexity with an improved control of the multiplicative constant factor in the asymptotic analysis. In this context, we developed novel techniques for estimation of parameters needed in our MLMC algorithms, such as the variance of the difference between consecutive approximations. These techniques take particular care of the deepest levels, where for efficiency reasons only few realizations are available to produce essential estimates. Moreover, we show the asymptotic normality of the statistical error in the MLMC estimator, justifying in this way our error estimate that allows prescribing both the required accuracy and confidence level in the final result. We present several examples to illustrate the above results and the corresponding computational savings.

References

  1. A Continuation Multilevel Monte Carlo algorithm, by N. Collier, A.-L. Haji-Ali, F. Nobile, E. von Schwerin and R. Tempone. BIT Numer. Math., 55, pp. 399-432, 2015.
  2. Optimization of mesh hierarchies in Multilevel Monte Carlo samplers of SDEs and PDEs with stochastic coefficients, by A.-L. Haji-Ali, F. Nobile, E. von Schwerin and R. Tempone. Stochastic Partial Differential Equations: Analysis and Computations, Vol. 4, Issue 1, Pages 76-112, 2016.
  3. Implementation and Analysis of an Adaptive Multi-Level Monte Carlo Algorithm, by H. Hoel, E. von Schwerin, A. Szepessy, and R. Tempone. Monte Carlo Methods and Applications, 20(1), pp. 1-41, 2014.
  4. Multilevel Hybrid Chernoff Tau-leap, by A. Moraes, R. Tempone and P. Vilanova. BIT Numerical Mathematics, Volume 56, Issue 1, pp 189-239, 2016.
  5. A multilevel adaptive reaction-splitting simulation method for stochastic reaction networks, by A. Moraes, R. Tempone and P. Vilanova. arXiv:1406.1989v1. To appear in SIAM Journal on Scientific Computing (SISC), 2016.
  6. Multi-level drift-implicit tau-leap, by C. Ben Hammouda, A. Moraes and R. Tempone. arXiv:1512.00721. To appear in the Journal of Numerical Algorithms, 2016.

Multi-index Monte Carlo and Multi-index Stochastic Collocation

Raúl Tempone
King Abdullah University of Science and Technology (KAUST)

We describe and analyze the Multi-Index Monte Carlo (MIMC) and the Multi-Index Stochastic Collocation method (MISC) for computing statistics of the solution of a PDE with random data. MIMC 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. Instead of using first-order differences as in MLMC, MIMC uses mixed differences to reduce the variance of the hierarchical differences dramatically. These mixed differences yield 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 convergence. On the same vein, MISC is a deterministic combination technique based on mixed differences of spatial approximations and quadratures over the space of random data. Provided enough mixed regularity, MISC can achieve better complexity than MIMC. Moreover, we show that, in the optimal case, the convergence rate of MISC is only dictated by the convergence of the deterministic solver applied to a one-dimensional spatial problem. We propose optimization procedures to select the most effective mixed differences to include in MIMC and MISC. Such optimization is a crucial step that allows us to make MIMC and MISC computationally efficient. We finally show the effectiveness of MIMC and MISC in some computational tests, including PDEs with random coefficients and Stochastic Particle Systems.

References

  1. Multi-Index Stochastic Collocation for random PDEs, by A. L. Haji Ali, F. Nobile, L. Tamellini and R. Tempone. To appear in Computers and Mathematics with Applications, 2016.
  2. Multi-index Stochastic Collocation convergence rates for random PDEs with parametric regularity, by A. Haji-Ali, F. Nobile, L. Tamellini, R. Tempone, Computers and Mathematics with Applications, Vol. 306, pp. 95-122, 2016.
  3. Multi Index Monte Carlo: When Sparsity Meets Sampling”, by A.-L. Haji-Ali, F. Nobile, and R. Tempone. Numerische Mathematik, Vol. 132(4), Pages 767-806, 2016.