Iterative Particle Approximation for McKean-Vlasov SDEs with application to Multilevel Monte Carlo estimation

Łukasz Szpruch, Shuren Tan, Alvin TsearXiv 2017 · DOI · arXiv

Abstract

The mean field limits of systems of interacting diffusions, often referred to as stochastic interacting particle systems (SIPS), have been a cornerstone of probabilistic modeling since the work of McKean. While these systems provide probabilistic representations for various nonlinear and nonlocal partial differential equations (PDEs), they present significant challenges for Monte Carlo simulation. The primary difficulty arises from the nonlinear dependence of the bias on the statistical error through the approximation of the law of the process, coupled with the fact that particles are not independent. This dependence renders classical variance reduction techniques, such as Multilevel Monte Carlo (MLMC), difficult to apply directly. In this work, we introduce an alternative iterative particle representation inspired by Sznitman’s fixed-point argument. This representation shares the same mean field limit as classical SIPS but allows for the decomposition of statistical error and approximation bias. We establish a general framework to study the integrability and regularity of this iterated system and prove its weak convergence to McKean-Vlasov SDEs (MVSDEs). By combining this iterative system with MLMC, we demonstrate a reduction in computational complexity by an order of magnitude. Furthermore, our analysis extends to state-dependent functionals and utilizes weighted norms to characterize error.

Introduction

McKean-Vlasov Stochastic Differential Equations (MVSDEs) describe the evolution of particles where the drift and diffusion coefficients depend not only on the particle's own state but also on the distribution (the law) of the entire population. These equations are vital for modeling mean-field phenomena in physics, biology, and finance, and they serve as a bridge to solving non-linear PDEs like the Fokker-Planck equation.

Despite their utility, simulating MVSDEs is computationally demanding. The standard approach involves Stochastic Interacting Particle Systems (SIPS), where $N$ particles interact with one another. This leads to two primary issues:

  1. Quadratic Complexity: A system of $N$ particles typically requires $O(N^2)$ operations per time step due to pairwise interactions.
  2. Dependency Constraints: Because particles in a SIPS are dependent, standard variance reduction techniques like Multilevel Monte Carlo (MLMC)—which require independent samples—cannot be applied in a straightforward manner. Consequently, achieving a root mean square error of $\epsilon$ using standard SIPS scales at a prohibitive $O(\epsilon^{-5})$.

The Iterative Particle Method

To overcome these limitations, this paper proposes a novel Iterative Multilevel Particle Method. The core innovation is the shift from a single interacting system to a sequence of Picard-style iterations.

Picard Iteration for Measures

Instead of allowing particles to interact in real-time, the method uses an iterative scheme. In each iteration $m$, the particles evolve based on the empirical distribution calculated from the previous iteration ($m-1$). This approach is inspired by Sznitman’s fixed-point argument, which is traditionally used to prove the existence of solutions rather than as a computational tool.

Restoring Independence

The breakthrough of this iterative approach is conditional independence. Because the particles in the current iteration only reference the fixed results of the previous iteration, they are independent of one another given the previous state. This independence is the key that unlocks the use of MLMC.

Nested Multilevel Monte Carlo

With independence restored, the authors nest MLMC within the iterative process. By using a hierarchy of time-discretization levels to estimate the expectations required for the next Picard step, the variance of the estimator is significantly reduced. The paper provides a rigorous error analysis using both uniform and weighted norms to prove the weak convergence of this iterative system to the true McKean-Vlasov limit.

Complexity and Key Results

The primary advantage of the iterative MLMC approach is its efficiency. The authors prove that this method achieves a mean-square error of $\epsilon^2$ with a computational complexity of $O(\epsilon^{-4} |\log \epsilon|^3)$. Compared to the $O(\epsilon^{-5})$ complexity of standard interacting particle systems, this represents a full order of magnitude improvement. In specific cases involving non-interacting kernels, the complexity can drop even further to $O(\epsilon^{-2} |\log \epsilon|^2)$.

Furthermore, this work distinguishes itself by handling state-dependent functionals. While much of the existing MLMC literature focuses on simple scalar outputs, this framework accommodates functionals that depend on the entire path or state of the system, making it applicable to a broader range of complex physical simulations.

Numerical Validation

The authors evaluated the algorithm using three distinct numerical benchmarks:

  1. The Kuramoto Model: A standard model for synchronization in physical and biological systems.
  2. Polynomial Drift Model: A case designed to test the algorithm's robustness against violations of standard regularity assumptions.
  3. Viscous Burgers Equation: A fundamental PDE in fluid dynamics. The method was tested here in a discontinuous (non-Lipschitz) setting, demonstrating that the approach remains effective even when strict mathematical assumptions are not fully met.

Conclusion and Future Directions

This research provides a practical and theoretically sound framework for the simulation of McKean-Vlasov SDEs. By repurposing the fixed-point argument into a computational strategy, the authors have bypassed the $O(N^2)$ bottleneck and enabled the use of MLMC for mean-field problems.

Future work may focus on extending the formal theory to singular kernels, such as those found in plasma physics, where the current "Ker-Reg" (smoothness) assumptions do not hold. Additionally, while MLMC is robust, the "curse of dimensionality" remains a factor when approximating measures in very high-dimensional spaces. Optimizing the schedule for increasing the number of particles ($N_m$) across Picard iterations also presents a promising path for further reducing computational overhead.

Summary updated

Abstract

The mean field limits of systems of interacting diffusions (also called stochastic interacting particle systems (SIPS)) have been intensively studied since McKean \cite{mckean1966class}. The interacting diffusions pave a way to probabilistic representations for many important nonlinear/nonlocal PDEs, but provide a great challenge for Monte Carlo simulations. This is due to the nonlinear dependence of the bias on the statistical error arising through the approximation of the law of the process. This and the fact that particles/diffusions are not independent render classical variance reduction techniques not directly applicable and consequently make simulations of interacting diffusions prohibitive. In this article, we provide an alternative iterative particle representation, inspired by the fixed point argument by Sznitman \cite{sznitman1991topics}. This new representation has the same mean field limit as the classical SIPS. However, unlike classical SIPS, it also allows decomposing the statistical error and the approximation bias. We develop a general framework to study integrability and regularity properties of the iterated particle system. Moreover, we establish its weak convergence to the McKean-Vlasov SDEs (MVSDEs). One of the immediate advantages of iterative particle system is that it can be combined with the Multilevel Monte Carlo (MLMC) approach for the simulation of MVSDEs. We proved that the MLMC approach reduces the computational complexity of calculating expectations by an order of magnitude. Another perspective on this work is that we analyse the error of nested Multilevel Monte Carlo estimators, which is of independent interest. Furthermore, we work with state dependent functionals, unlike scalar outputs which are common in literature on MLMC. The error analysis is carried out in uniform, and what seems to be new, weighted norms.
BibTeX
@misc{szpruch2017iterative,
  author = {Łukasz Szpruch and Shuren Tan and Alvin Tse},
  title = {{Iterative Particle Approximation for McKean-Vlasov SDEs with application to Multilevel Monte Carlo estimation}},
  year = {2017},
  eprint = {1706.00907},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1706.00907},
}
Figure