Search

This work introduces a novel approach that combines the multi-index Monte Carlo (MC) method with importance sampling (IS) to estimate rare event quantities expressed as an expectation of a smooth observable of solutions to a broad class of McKean-Vlasov stochastic differential equations. We extend the double loop Monte Carlo (DLMC) estimator, previously introduced in our works (Ben Rached et al., 2022a,b), to the multi-index setting. We formulate a new multi-index DLMC estimator and conduct a comprehensive cost-error analysis, leading to improved complexity results. To address rare events, an importance sampling scheme is applied using stochastic optimal control of the single level DLMC estimator. This combination of IS and multi-index DLMC not only reduces computational complexity by two orders but also significantly decreases the associated constant compared to vanilla MC. The effectiveness of the proposed multi-index DLMC estimator is demonstrated using the Kuramoto model from statistical physics. The results confirm a reduced complexity from $\mathcal{O}(\mathrm{TOL}_{\mathrm{r}}^{-4})$ for the single level DLMC estimator (Ben Rached et al., 2022a) to $\mathcal{O}(\mathrm{TOL}_{\mathrm{r}}^{-2} (\log \mathrm{TOL}_{\mathrm{r}}^{-1})^2)$ for the considered example, while ensuring accurate estimation of rare event quantities within the prescribed relative error tolerance $\mathrm{TOL}_\mathrm{r}$., Comment: Extension to works 2207.06926 and 2208.03225

This work combines multilevel Monte Carlo (MLMC) with importance sampling to estimate rare-event quantities that can be expressed as the expectation of a Lipschitz observable of the solution to a broad class of McKean--Vlasov stochastic differential equations. We extend the double loop Monte Carlo (DLMC) estimator introduced in this context in (Ben Rached et al., 2023) to the multilevel setting. We formulate a novel multilevel DLMC estimator and perform a comprehensive cost-error analysis yielding new and improved complexity results. Crucially, we devise an antithetic sampler to estimate level differences guaranteeing reduced computational complexity for the multilevel DLMC estimator compared with the single-level DLMC estimator. To address rare events, we apply the importance sampling scheme, obtained via stochastic optimal control in (Ben Rached et al., 2023), over all levels of the multilevel DLMC estimator. Combining importance sampling and multilevel DLMC reduces computational complexity by one order and drastically reduces the associated constant compared to the single-level DLMC estimator without importance sampling. We illustrate the effectiveness of the proposed multilevel DLMC estimator on the Kuramoto model from statistical physics with Lipschitz observables, confirming the reduced complexity from $\mathcal{O}(\mathrm{TOL}_{\mathrm{r}}^{-4})$ for the single-level DLMC estimator to $\mathcal{O}(\mathrm{TOL}_{\mathrm{r}}^{-3})$ while providing a feasible estimate of rare-event quantities up to prescribed relative error tolerance $\mathrm{TOL}_{\mathrm{r}}$., Comment: Follow-up to arXiv:2207.06926

This paper investigates Monte Carlo (MC) methods to estimate probabilities of rare events associated with solutions to the $d$-dimensional McKean-Vlasov stochastic differential equation (MV-SDE). MV-SDEs are usually approximated using a stochastic interacting $P$-particle system, which is a set of $P$ coupled $d$-dimensional stochastic differential equations (SDEs). Importance sampling (IS) is a common technique for reducing high relative variance of MC estimators of rare-event probabilities. We first derive a zero-variance IS change of measure for the quantity of interest by using stochastic optimal control theory. However, when this change of measure is applied to stochastic particle systems, it yields a $P \times d$-dimensional partial differential control equation (PDE), which is computationally expensive to solve. To address this issue, we use the decoupling approach introduced in [dos Reis et al., 2023], generating a $d$-dimensional control PDE for a zero-variance estimator of the decoupled SDE. Based on this approach, we develop a computationally efficient double loop MC (DLMC) estimator. We conduct a comprehensive numerical error and work analysis of the DLMC estimator. As a result, we show optimal complexity of $\mathcal{O}(\mathrm{TOL}_{\mathrm{r}}^{-4})$ with a significantly reduced constant to achieve a prescribed relative error tolerance $\mathrm{TOL}_{\mathrm{r}}$. Subsequently, we propose an adaptive DLMC method combined with IS to numerically estimate rare-event probabilities, substantially reducing relative variance and computational runtimes required to achieve a given $\mathrm{TOL}_{\mathrm{r}}$ compared with standard MC estimators in the absence of IS. Numerical experiments are performed on the Kuramoto model from statistical physics.