New particle representations for ergodic McKean-Vlasov SDEs

Houssam Alrachid, Mireille Bossy, Cristiano Ricci, Łukasz Szpruch

Abstract

The aim of this paper is to introduce several new particle representations for ergodic McKean-Vlasov SDEs. We construct new algorithms by leveraging recent progress in weak convergence analysis of interacting particle systems. We present a detailed analysis of errors and associated costs of various estimators, highlighting key differences between long-time simulations of linear (classical SDEs) versus non-linear (McKean-Vlasov SDEs) processes.

Introduction

In computational physics, finance, and machine learning, a fundamental challenge is sampling from a target probability distribution $\pi$. A standard approach involves designing a stochastic differential equation (SDE) whose invariant measure is $\pi$. While classical "linear" SDEs—where a particle's drift depends only on its own position—are well-understood, many modern applications require McKean-Vlasov SDEs. These are "non-linear" processes where the movement of a particle depends on the distribution of the entire population.

Simulating these systems typically requires an interacting particle system (IPS) of $N$ particles. However, because each particle interacts with every other particle, the computational complexity scales quadratically ($O(N^2)$). This paper addresses the bottleneck of long-time simulations for such systems, proposing novel representations that significantly reduce the computational burden required to reach a steady state.

The Challenge: Non-Linearity and the Bias-Variance Trap

In classical SDEs, the statistical error is primarily driven by variance, which can be mitigated by running independent trials. In McKean-Vlasov systems, the situation is more complex. The finite number of particles $N$ introduces a "bias" into the dynamics themselves because the estimated distribution is only an approximation of the true law. This creates a non-linear coupling between the statistical error and the system's evolution, making variance reduction significantly more difficult than in the linear case.

Proposed Particle Representations

To overcome the $O(N^2)$ scaling and the bias-variance trap, we introduce and analyze three primary methodologies:

1. Averaged Ergodic Average (AEA)

Traditional Monte Carlo approaches often take a snapshot of $N$ particles at a sufficiently large time $T$. The AEA method instead averages the trajectories of all $N$ particles over a time interval. This "double averaging"—across both the particle ensemble (space) and the trajectory (time)—allows the algorithm to achieve the same level of accuracy with a significantly smaller number of particles.

2. Ensemble AEA (C-AEA)

To better utilize modern parallel computing architectures, we propose the Ensemble or Cloud AEA. This method groups particles into $M$ independent ensembles. By balancing the number of ensembles against the number of particles within each ensemble, we can optimize the trade-off between statistical bias and variance while ensuring the workload is perfectly distributable across processors.

3. Self-Interacting Diffusions (SID)

Perhaps the most significant conceptual shift is the introduction of Self-Interacting Diffusions. Rather than simulating a massive swarm of particles to approximate the population distribution, we simulate a single particle (or a very small group) that interacts with its own historical trajectory. The particle's past serves as a proxy for the distribution of the population. This approach potentially bypasses the need for large-scale interacting systems entirely.

Cost-Benefit Analysis

We evaluate these methods based on the computational cost required to achieve a prescribed error tolerance $\epsilon$. Our analysis reveals substantial efficiency gains:

  • Naive Monte Carlo (MCA): The computational cost scales as $O(\epsilon^{-5})$.
  • Averaged Ergodic Average (AEA): Reduces the cost to $O(\epsilon^{-4})$. For an error tolerance of $\epsilon = 0.01$, this represents a 100x improvement in efficiency.
  • Self-Interacting Systems (SID): Achieve a cost of approximately $O(\epsilon^{-4} \log(\epsilon^{-1}))$. This confirms that self-interaction is a mathematically viable and computationally efficient alternative to large-scale interacting particle systems.

Conclusion and Future Directions

This work demonstrates that leveraging the ergodic properties of McKean-Vlasov SDEs can lead to significant algorithmic improvements. While we have established rigorous cost bounds, some theoretical challenges remain, particularly regarding uniform-in-time weak convergence in non-convex settings.

Future research will focus on relaxing the "convexity at infinity" requirements for the drift and exploring the integration of Multilevel Monte Carlo (MLMC) strategies. Combining MLMC with these particle representations could potentially reduce the computational cost of non-linear SDEs to the level of standard, non-interacting SDEs, further opening the door for high-dimensional sampling in complex systems.

Summary updated

Abstract

The aim of this paper is to introduce several new particle representations for ergodic McKean-Vlasov SDEs. We construct new algorithms by leveraging recent progress in weak convergence analysis of interacting particle system. We present detailed analysis of errors and associated costs of various estimators, highlighting key differences between long-time simulations of linear (classical SDEs) versus non-linear (Mckean-Vlasov SDEs) process.
BibTeX
@inproceedings{alrachid2019new,
  author = {Houssam Alrachid and Mireille Bossy and Cristiano Ricci and Łukasz Szpruch},
  title = {{New particle representations for ergodic McKean-Vlasov SDEs}},
  booktitle = {ESAIM},
  year = {2019},
  doi = {10.1051/proc/201965068},
}
Figure