Multilevel Importance Sampling for McKean-Vlasov Stochastic Differential Equation

This work combines multilevel Monte Carlo methods with importance sampling (IS) to estimate rare event quantities that can be expressed as the expectation of a Lipschitz observable of the solution to the McKean-Vlasov stochastic differential equation. We first extend the double loop Monte Carlo (DLMC) estimator, introduced in this context in our previous work [Ben Rached et al. 2022], to the multilevel setting. We formulate a novel multilevel DLMC (MLDLMC) estimator, and perform a comprehensive work-error analysis yielding new and improved complexity results. Crucially, we also devise an antithetic sampler to estimate level differences that guarantees reduced work complexity for the MLDLMC estimator compared with the single level DLMC estimator. To tackle rare events, we apply the same single level IS scheme, obtained via stochastic optimal control in [Ben Rached et al. 2022], over all levels of the MLDLMC estimator. Combining IS and MLDLMC not only reduces computational complexity by one order, but also drastically reduces the associated constant, ensuring feasible estimates for rare event quantities. We illustrate effectiveness of proposed MLDLMC estimator on the Kuramoto model from statistical physics with Lipschitz observables, confirming reduced complexity from $\mathcal{O}(TOL_r^{-4})$ for the single level DLMC estimator to $\mathcal{O}(TOL_r^{-3})$ while providing feasible estimation for rare event quantities up to the prescribed relative error tolerance $TOL_r$.