Convergence of a single-ensemble multilevel scheme for McKean-Vlasov SDEs

Source abstract

Numerically solving McKean-Vlasov stochastic differential equations is computationally challenging due to the compounding costs of discretizing in time and in the distribution of the solution. Multilevel ideas have been proposed to provide speed-ups. In this work, we study the multilevel Monte Carlo method proposed by Ricketson (2015) for equations whose drift and diffusion terms depend on the law of the solution $X_t$ through the expectation $E[R(X_t)]$. The scheme follows the single-ensemble paradigm, where particles interact across levels at each timestep. While cross-level feedback makes this scheme attractive in practice, the correlations it introduces have so far confined its cost-error analysis to a model problem with linear drift, deterministic diffusion, and $R$ the identity. We use additional coarse particles to enforce geometrically decaying coupling errors towards the coarser levels. This allows us to prove our main contribution, an $L^p$-error of $O(ε)$ at cost $O(ε^{-2-δ})$ for any $p\ge2$ and $δ>0$ (with a constant that grows as $δ\to0$), assuming only global Lipschitz bounds on the drift, the diffusion, and $R$. An exploratory experiment is consistent with the derived rates and suggests that in practice the constant does not grow significantly for small $δ$. Our methodology and proof strategy may also be useful for other single-ensemble multilevel schemes, such as multilevel ensemble Kalman filters.