BIT Numerical Mathematics

, Volume 55, Issue 2, pp 399–432

A continuation multilevel Monte Carlo algorithm

Article

Abstract

We propose a novel Continuation Multi Level Monte Carlo (CMLMC) algorithm for weak approximation of stochastic models. The CMLMC algorithm solves the given approximation problem for a sequence of decreasing tolerances, ending when the required error tolerance is satisfied. CMLMC assumes discretization hierarchies that are defined a priori for each level and are geometrically refined across levels. The actual choice of computational work across levels is based on parametric models for the average cost per sample and the corresponding variance and weak error. These parameters are calibrated using Bayesian estimation, taking particular notice of the deepest levels of the discretization hierarchy, where only few realizations are available to produce the estimates. The resulting CMLMC estimator exhibits a non-trivial splitting between bias and statistical contributions. We also show the asymptotic normality of the statistical error in the MLMC estimator and justify in this way our error estimate that allows prescribing both required accuracy and confidence in the final result. Numerical results substantiate the above results and illustrate the corresponding computational savings in examples that are described in terms of differential equations either driven by random measures or with random coefficients.

Keywords

Multilevel Monte Carlo Monte Carlo Partial differential equations with random data Stochastic differential equations Bayesian inference

65C05 65N22

References

1. 1.
Amestoy, P.R., Duff, I.S., L’Excellent, J.Y., Koster, J.: A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM J. Matrix Anal. Appl. 23, 15–41 (2001)
2. 2.
Amestoy, P.R., Guermouche, A., L’Excellent, J.Y., Pralet, S.: Hybrid scheduling for the parallel solution of linear systems. Parallel Comput. 32(2), 136–156 (2006)
3. 3.
Babuška, I., Nobile, F., Tempone, R.: A stochastic collocation method for elliptic partial differential equations with random input data. SIAM Rev. 52(2), 317–355 (2010)
4. 4.
Balay, S., Brown, J., Buschelman, K., Gropp, W.D., Kaushik, D., Knepley, M.G., McInnes, L.C., Smith, B.F., Zhang, H.: PETSc Web page (2013). http://www.mcs.anl.gov/petsc
5. 5.
Barth, A., Schwab, C., Zollinger, N.: Multi-level Monte Carlo finite element method for elliptic PDEs with stochastic coefficients. Numer. Math. 119(1), 123–161 (2011)
6. 6.
Charrier, J., Scheichl, R., Teckentrup, A.: Finite element error analysis of elliptic PDEs with random coefficients and its application to multilevel Monte Carlo methods. SIAM J. Numer. Anal. 51(1), 322–352 (2013)
7. 7.
Cliffe, K., Giles, M., Scheichl, R., Teckentrup, A.: Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients. Comput. Vis. Sci. 14(1), 3–15 (2011)
8. 8.
Collier, N., Dalcin, L., Calo, V.: PetIGA: high-performance isogeometric analysis. (2013). http://arxiv.org/abs/1305.4452
9. 9.
Dalcin, L., Collier, N.: PetIGA: a framework for high performance isogeometric analysis (2013). https://bitbucket.org/dalcinl/petiga
10. 10.
Durrett, R.: Probability: Theory and Examples, 2nd edn. Duxbury Press, Belmont (1996)Google Scholar
11. 11.
Giles, M.: Improved multilevel Monte Carlo convergence using the Milstein scheme. In: Monte Carlo and quasi-Monte Carlo methods 2006, pp. 343–358. Springer, Berlin (2008)Google Scholar
12. 12.
Giles, M.: Multilevel Monte Carlo path simulation. Oper. Res. 56(3), 607–617 (2008)
13. 13.
Giles, M., Reisinger, C.: Stochastic finite differences and multilevel Monte Carlo for a class of SPDEs in finance. SIAM J. Financ. Math. 3(1), 572–592 (2012)
14. 14.
Giles, M., Szpruch, L.: Antithetic multilevel Monte Carlo estimation for multidimensional SDEs. In: Monte Carlo and Quasi-Monte Carlo Methods 2012. Springer, Berlin (2013)Google Scholar
15. 15.
Giles, M., Szpruch, L.: Multilevel Monte Carlo methods for applications in finance, pp. 3–48. World Scientific, Singapore (2013)Google Scholar
16. 16.
Giles, M., Szpruch, L.: Antithetic multilevel Monte Carlo estimation for multi-dimensional SDEs without Lévy area simulation. Ann. Appl. Probab. (2014)Google Scholar
17. 17.
Glasserman, P.: Monte Carlo methods in financial engineering. Applications of Mathematics (New York), vol. 53. Stochastic Modelling and Applied Probability. Springer, New York (2004)Google Scholar
18. 18.
Heinrich, S.: Monte Carlo complexity of global solution of integral equations. J. Complex. 14(2), 151–175 (1998)
19. 19.
Heinrich, S., Sindambiwe, E.: Monte Carlo complexity of parametric integration. J. Complex. 15(3), 317–341 (1999)
20. 20.
Hoel, H., Schwerin, E.v., Szepessy, A., Tempone, R.: Adaptive multilevel Monte Carlo simulation. In: Engquist, B., Runborg, O., Tsai, Y.H. (eds.) Numerical Analysis of Multiscale Computations, no. 82 in Lecture Notes in Computational Science and Engineering, pp. 217–234. Springer, New York (2012)Google Scholar
21. 21.
Hunter, J.D.: Matplotlib: a 2D graphics environment. Comput. Sci. Eng. 9(3), 90–95 (2007)
22. 22.
Jouini, E., Cvitanić, J., Musiela, M. (eds.): Handbooks in Mathematical Finance. Option Pricing, Interest Rates and Risk Management. Cambridge University Press, Cambridge (2001)Google Scholar
23. 23.
Karatzas, I., Shreve, S.E.: Brownian Motion and Stochastic Calculus, Graduate Texts in Mathematics, 2nd edn, vol. 113. Springer, New York (1991)Google Scholar
24. 24.
Kebaier, A.: Statistical Romberg extrapolation: a new variance reduction method and applications to options pricing. Ann. Appl. Probab. 14(4), 2681–2705 (2005)
25. 25.
Mordecki, E., Szepessy, A., Tempone, R., Zouraris, G.E.: Adaptive weak approximation of diffusions with jumps. SIAM J. Numer. Anal. 46(4), 1732–1768 (2008)
26. 26.
Øksendal, B.: Stochastic differential equations. Universitext, 5th edn. Springer, Berlin (1998)Google Scholar
27. 27.
Sivia, D.S., Skilling, J.: Data Analysis.: A Bayesian Tutorial, 2nd edn. Oxford University Press, Oxford (2006)Google Scholar
28. 28.
Szepessy, A., Tempone, R., Zouraris, G.E.: Adaptive weak approximation of stochastic differential equations. Commun. Pure Appl. Math. 54(10), 1169–1214 (2001)
29. 29.
Teckentrup, A.: Multilevel Monte Carlo methods and uncertainty quantification. PhD thesis, University of Bath (2013)Google Scholar
30. 30.
Teckentrup, A., Scheichl, R., Giles, M., Ullmann, E.: Further analysis of multilevel Monte Carlo methods for elliptic PDEs with random coefficients. Numer. Math. 125(3), 569–600 (2013)
31. 31.
Xia, Y., Giles, M.: Multilevel path simulation for jump-diffusion SDEs. In: Plaskota, L., Woźniakowski, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2010, pp. 695–708. Springer, Berlin (2012)Google Scholar

Authors and Affiliations

• Nathan Collier
• 1
• Abdul-Lateef Haji-Ali
• 2
Email author
• Fabio Nobile
• 3
• Erik von Schwerin
• 4
• Raúl Tempone
• 2
1. 1.Environmental Sciences Division, Oak Ridge National LabClimate Change Science Institute (CCSI)Oak RidgeUSA
2. 2.Applied Mathematics and Computational SciencesKAUSTThuwalSaudi Arabia
3. 3.MATHICSE-CSQI, EPF de LausanneLausanneSwitzerland
4. 4.Department of MathematicsKungliga Tekniska HögskolanStockholmSweden
{"ft_lang_label":"__label__en","ft_lang_prob":0.571873,"math_prob":0.73581964,"size":7896,"snap":"2019-26-2019-30","text_gpt3_token_len":2157,"char_repetition_ratio":0.15686771,"word_repetition_ratio":0.029411765,"special_character_ratio":0.26000506,"punctuation_ratio":0.29103535,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.97776276,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-06-17T00:49:50Z\",\"WARC-Record-ID\":\"<urn:uuid:fa753e6f-e496-4a72-ab6c-182a8e0062c6>\",\"Content-Length\":\"116606\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:7980f847-8d07-4915-9e58-151c01f3e76b>\",\"WARC-Concurrent-To\":\"<urn:uuid:09d76143-cd40-4145-b242-09bfcd963de4>\",\"WARC-IP-Address\":\"151.101.248.95\",\"WARC-Target-URI\":\"https://link.springer.com/article/10.1007/s10543-014-0511-3\",\"WARC-Payload-Digest\":\"sha1:QM2ASWRGL7U3ANK7UC4N2Q5NDHAX7HAV\",\"WARC-Block-Digest\":\"sha1:RZXONFX7I24JW75BKM25YUJV2TF2S62O\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-26/CC-MAIN-2019-26_segments_1560627998339.2_warc_CC-MAIN-20190617002911-20190617024911-00303.warc.gz\"}"}