×

Multilevel and multi-index Monte Carlo methods for the McKean-Vlasov equation. (English) Zbl 1387.65004

Summary: We address the approximation of functionals depending on a system of particles, described by stochastic differential equations (SDEs), in the mean-field limit when the number of particles approaches infinity. This problem is equivalent to estimating the weak solution of the limiting McKean-Vlasov SDE. To that end, our approach uses systems with finite numbers of particles and a time-stepping scheme. In this case, there are two discretization parameters: the number of time steps and the number of particles. Based on these two parameters, we consider different variants of the Monte Carlo and Multilevel Monte Carlo (MLMC) methods and show that, in the best case, the optimal work complexity of MLMC, to estimate the functional in one typical setting with an error tolerance of \(\text{TOL}\), is \(\mathcal O(\text{TOL}^{-3})\) when using the partitioning estimator and the Milstein time-stepping scheme. We also consider a method that uses the recent Multi-index Monte Carlo method and show an improved work complexity in the same typical setting of \(\mathcal O(\text{TOL}^{-2}\log (\text{TOL}^{-1})^2)\). Our numerical experiments are carried out on the so-called Kuramoto model, a system of coupled oscillators.

MSC:

65C05 Monte Carlo methods
65C30 Numerical solutions to stochastic differential and integral equations
65C35 Stochastic particle methods
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Acebrón, J.A., Bonilla, L.L., Vicente, C.J.P., Ritort, F., Spigler, R.: The Kuramoto model: a simple paradigm for synchronization phenomena. Rev. Mod. Phys. 77(1), 137 (2005) · doi:10.1103/RevModPhys.77.137
[2] Bossy, M., Talay, D.: Convergence rate for the approximation of the limit law of weakly interacting particles: application to the Burgers equation. Ann. Appl. Probab. 6(3), 818-861 (1996) · Zbl 0860.60038 · doi:10.1214/aoap/1034968229
[3] Bossy, M., Talay, D.: A stochastic particle method for the McKean-Vlasov and the Burgers equation. Math. Comput. Am. Math. Soc. 66(217), 157-192 (1997) · Zbl 0854.60050 · doi:10.1090/S0025-5718-97-00776-X
[4] Bujok, K., Hambly, B., Reisinger, C.: Multilevel simulation of functionals of Bernoulli random variables with application to basket credit derivatives. Methodol. Comput. Appl. Probab. 73, 1-26 (2013) · Zbl 1327.65003
[5] Carrier, J., Greengard, L., Rokhlin, V.: A fast adaptive multipole algorithm for particle simulations. SIAM J. Sci. Stat. Comput. 9(4), 669-686 (1988) · Zbl 0656.65004 · doi:10.1137/0909044
[6] 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) · Zbl 1241.65012 · doi:10.1007/s00791-011-0160-x
[7] Collier, N., Haji-Ali, A.-L., Nobile, F., von Schwerin, E., Tempone, R.: A continuation multilevel Monte Carlo algorithm. BIT Numer. Math. 55(2), 399-432 (2015) · Zbl 1317.65030 · doi:10.1007/s10543-014-0511-3
[8] Dobramysl, U., Rüdiger, S., Erban, R.: Particle-based multiscale modeling of calcium puff dynamics. Multiscale Model. Simul. 14(3), 997-1016 (2016) · Zbl 1352.65022 · doi:10.1137/15M1015030
[9] Erban, R., Haskovec, J.: From individual to collective behaviour of coupled velocity jump processes: a locust example. Kinet. Relat. Models 5(4), 817-842 (2012) · Zbl 1397.60077 · doi:10.3934/krm.2012.5.817
[10] Erban, R., Haskovec, J., Sun, Y.: A Cucker-Smale model with noise and delay. SIAM J. Appl. Math. 76(4), 1535-1557 (2016) · Zbl 1345.60063 · doi:10.1137/15M1030467
[11] Gärtner, J.: On the McKean-Vlasov limit for interacting diffusions. Mathematische Nachrichten 137(1), 197-248 (1988) · Zbl 0678.60100 · doi:10.1002/mana.19881370116
[12] Giles, MB; Keller, A. (ed.); Heinrich, S. (ed.); Niederreiter, H. (ed.), Improved multilevel Monte Carlo convergence using the Milstein scheme, 343-358 (2008), Berlin · Zbl 1141.65321 · doi:10.1007/978-3-540-74496-2_20
[13] Giles, M.B.: Multilevel Monte Carlo path simulation. Oper. Res. 56(3), 607-617 (2008b) · Zbl 1167.65316 · doi:10.1287/opre.1070.0496
[14] Giles, M.B.: Multilevel Monte Carlo methods. Acta Numer. 24, 259-328 (2015) · Zbl 1316.65010 · doi:10.1017/S096249291500001X
[15] Giles, M.B., Szpruch, L.: Antithetic multilevel Monte Carlo estimation for multi-dimensional SDEs without Lévy area simulation. Ann. Appl. Probab. 24(4), 1585-1620 (2014) · Zbl 1373.65007 · doi:10.1214/13-AAP957
[16] Greengard, L., Rokhlin, V.: A fast algorithm for particle simulations. J. Comput. Phys. 73(2), 325-348 (1987) · Zbl 0629.65005 · doi:10.1016/0021-9991(87)90140-9
[17] Haji-Ali, A.-L.: Pedestrian flow in the mean-field limit. King Abdullah University of Science and Technology (KAUST). http://hdl.handle.net/10754/250912 (2012)
[18] Haji-Ali, A.-L.: mimclib. https://github.com/StochasticNumerics/mimclib (2016) · Zbl 0860.60038
[19] Haji-Ali, A.-L., Nobile, F., Tempone, R.: Multi-index Monte Carlo: when sparsity meets sampling. Numer. Math. 132, 767-806 (2015a) · Zbl 1339.65009 · doi:10.1007/s00211-015-0734-5
[20] Haji-Ali, A.-L., Nobile, F., von Schwerin, E., Tempone, R.: Optimization of mesh hierarchies in multilevel Monte Carlo samplers. Stoch. Partial Differ. Equ. Anal. Comput. 4, 76-112 (2015b) · Zbl 1359.65013
[21] Heinrich, S.: Multilevel Monte Carlo methods. In: Large-Scale Scientific Computing, vol. 2179 of Lecture Notes in Computer Science. Springer, Berlin, pp. 58-67 (2001) · Zbl 1031.65005
[22] Helbing, D., Molnar, P.: Social force model for pedestrian dynamics. Phys. Rev. E 51(5), 4282 (1995) · doi:10.1103/PhysRevE.51.4282
[23] Kloeden, P.E., Platen, E.: Numerical solution of stochastic differential equations. Springer, Berlin (1992). doi:10.1007/978-3-662-12616-5 · Zbl 0752.60043
[24] Kolokoltsov, V., Troeva, M.: On the mean field games with common noise and the Mckean-Vlasov SPDEs. ArXiv preprint arXiv:1506.04594 (2015) · Zbl 1415.60075
[25] Pierre Del Moral, A.K., Tugaut, J.: On the stability and the uniform propagation of chaos of a class of extended Ensemble Kalman-Bucy filters. SIAM J. Control Optim. 55(1), 119-155 (2016) · Zbl 1356.60065 · doi:10.1137/16M1087497
[26] Ricketson, L.: A multilevel Monte Carlo method for a class of McKean-Vlasov processes. ArXiv preprint arXiv:1508.02299 (2015)
[27] Rosin, M., Ricketson, L., Dimits, A., Caflisch, R., Cohen, B.: Multilevel Monte Carlo simulation of Coulomb collisions. J. Comput. Phys. 274, 140-157 (2014) · Zbl 1351.82085
[28] Sznitman, A.-S.: Topics in propagation of chaos. In: Ecole d’été de probabilités de Saint-Flour XIX-1989. Springer, pp. 165-251 (1991) · Zbl 1345.60063
[29] Tange, O.: GNU parallel—the command-line power tool. login USENIX Mag. 36(1), 42-47 (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.