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 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

Sampling from complex, high-dimensional probability distributions is a cornerstone of modern statistics and machine learning. Traditionally, researchers have relied on "linear" Stochastic Differential Equations (SDEs), such as Langevin dynamics, where particles move independently. However, a new class of algorithms based on gradient flows utilizes McKean-Vlasov SDEs. In these non-linear systems, the "drift" or movement of a particle depends on the current law (the overall distribution) of the entire population.

While powerful, McKean-Vlasov SDEs present a significant computational challenge: we cannot simulate the "law" directly. Instead, we must approximate it using a system of $N$ interacting particles. This creates two massive hurdles:

  1. Computational Cost: Because every particle interacts with every other particle, the cost per time step scales as $O(N^2)$.
  2. Statistical Bias: In these non-linear systems, statistical errors in the particle distribution create a "bias" that feeds back into the dynamics. Standard variance reduction techniques often fail because the particles are no longer independent.

Proposed Methodology

This paper introduces and analyzes several novel representations to approximate the invariant measure (the steady-state distribution) of these systems more efficiently than traditional methods.

Averaged Ergodic Average (AEA)

Instead of relying solely on a spatial average of $N$ particles at a final time $T$, the AEA method averages the particles over both space and time. This "double averaging" helps smooth out the specific bias introduced by the empirical measure of the interacting system.

Self-Interacting Diffusions

This is a "one-particle" approach. Rather than simulating a massive population, a single particle's movement depends on its own past history (its "occupation measure"). The authors demonstrate that under certain conditions, this single self-interacting path converges to the same equilibrium as the full McKean-Vlasov system, potentially bypassing the $N^2$ interaction cost.

Ensemble and Hybrid Approaches

To further refine these methods, the authors propose Ensemble AEA (generating $M$ independent ensembles of $N$ particles) and Ensemble Self-Interacting (CS-AEA). These hybrid approaches allow for better error balancing and are designed to take full advantage of parallel computing architectures.

Key Insights and Theoretical Results

The Decoupling of Bias and Variance

In classical, linear SDEs, time averaging and space averaging (increasing the number of particles) affect variance in a similar fashion. A key insight of this work is that in McKean-Vlasov systems, these factors are decoupled. Time averaging is uniquely powerful at reducing the specific type of bias caused by particle interaction, which is not the case in linear systems.

Order of Magnitude Speedup

The paper provides some of the first "uniform-in-time" weak convergence bounds for these systems, ensuring that error estimates remain valid even for infinitely long simulations. The computational gains are substantial:

  • Standard Monte Carlo Average (MCA): Cost $\approx \log(\epsilon^{-1})\epsilon^{-5}$.
  • Proposed AEA: Cost $\approx \epsilon^{-4}$.
  • Ensemble Self-Interacting: Cost $\approx \epsilon^{-4} \log(\epsilon^{-1})$.

By dropping the cost from $O(\epsilon^{-5})$ to $O(\epsilon^{-4})$ to reach an error tolerance of $\epsilon$, the authors provide a full power-of-ten improvement in efficiency for high-dimensional simulations.

The "Forgetting" Property

The efficiency of these algorithms relies on the system being ergodic. The authors show that these systems eventually "forget" their initial poor approximations. By leveraging this property, self-interacting paths become increasingly accurate as the simulation progresses, allowing the estimator to converge to the true invariant measure.

Limitations and Future Directions

While the proposed algorithms offer significant speedups, the authors acknowledge certain theoretical and practical limitations:

  • Theoretical Gaps: Some theoretical bounds regarding uniform-in-time particle errors require more rigorous PDE-based research to fully solidify.
  • Structural Assumptions: The efficiency of self-interacting diffusions depends on specific properties of the drift, such as dissipativity, which may not be present in all complex physical or biological models.
  • Future Work: The authors suggest that combining these new representations with Multilevel Monte Carlo (MLMC) strategies could potentially reduce the cost of simulating interacting systems to the same level as simulating independent particles, further revolutionizing the field of non-linear SDE simulation.

Summary updated

Abstract

The aim of this paper is to introduce several new particle representations for \textit{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