Source-linked AI summary
Convergence of a single-ensemble multilevel scheme for McKean-Vlasov SDEs
Arne Bouillon, Giovanni Samaey
TL;DR
McKean–Vlasov SDE simulation is costly because it requires both time discretization and approximation of a law-dependent expectation. This paper adapts a single-ensemble multilevel scheme with geometrically decreasing coupling errors, and proves a near-O(ε^-2) cost rate under global Lipschitz assumptions.
Problem
Simulating McKean–Vlasov SDEs requires discretizing time and approximating E[R(X_t)], whose compounding costs rise as accuracy requirements tighten.
Source: §1 · p. 2Method
The scheme controls multilevel estimation error by requiring geometrically decreasing errors on coarser levels, whose sum is independent of the number of levels.
Source: §3.2 · p. 11, §5 · p. 14Results
For any δ > 0, the cost can be O(ε^-2-δ), with the constant increasing as q approaches 1.
Source: §3.2 · p. 8, §5 · p. 15Takeaways & Limitations
The geometrically decreasing-error approach may also be useful for other methods.
Source: §5 · p. 14The analysis is limited to globally Lipschitz coefficients and interaction through E[R(X_t)]; extensions to non-Lipschitz coefficients or more general interactions remain future work.
Source: §5 · p. 15
Abstract
from arXiv · showhide
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(\epsilon)$ at cost $O(\epsilon^{-2-\delta})$ for any $p\ge2$ and $\delta>0$ (with a constant that grows as $\delta\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 $\delta$. Our methodology and proof strategy may also be useful for other single-ensemble multilevel schemes, such as multilevel ensemble Kalman filters.
1 Introduction
McKean–Vlasov SDE simulation compounds time-discretization costs with the cost of approximating a law-dependent expectation. The paper develops a rigorous cost-error analysis for a single-ensemble multilevel scheme under global Lipschitz assumptions.
1 Introduction
- Time discretization and approximation of E[R(X_t)] multiply computational costs as accuracy requirements tighten.The expectation is approximated by simulating interacting particles and using their empirical distribution.Source: §1 · p. 2
1.1 Multilevel Monte Carlo
- Cross-level correlations make single-ensemble methods difficult to analyze, and prior cost-error analysis for the matching continuous-time scheme covers only a special case.The cited result treats linear drift, deterministic diffusion, and R as the identity; multiple-ensemble methods remove cross-level correlations but target different scopes.Source: §1.1 · p. 3
1.2 Objectives and contributions
- The contribution is to make the single-ensemble method from [21] amenable to rigorous cost-error analysis with two minor algorithmic changes and an arbitrarily small asymptotic cost penalty.The analysis assumes interaction through E[R(X_t)] and globally Lipschitz b, σ, R, and φ.Source: §1.2 · pp. 3–4
- For any p ≥ 2 and δ > 0, the scheme achieves Lp-error O(ε) at cost O(ε^-2-δ), using additional coarse particles to enforce geometrically decaying coupling errors.The error-bound constant grows as δ approaches zero; an experiment is reported to follow the predicted rates without this penalty.Source: §1.2 · p. 4
- The authors suggest their methodology may extend to more general settings, including multilevel ensemble Kalman filters.They describe this as a prospective application rather than an established result.Source: §1.2 · p. 4
2 The multilevel scheme
The scheme modifies the single-ensemble method by coupling adjacent levels and changing how particles interact across levels. Its multilevel estimate combines particles at different timesteps to approximate a quantity of interest.
2 The multilevel scheme
- Coupled fine-level particle pairs share Brownian motion and differ in timestep and interaction terms.The adjacent-level timestep ratio is generalized to Δt_(ℓ-1) = aΔt_ℓ for a > 1.Source: §2 · p. 4
- A particle at level ℓ interacts only with particles at levels ℓ and below, while higher-level particles see lower-level paths as piecewise constant.This replaces the interpolation of lower-level paths used in [21]; the scheme also uses more coarse particles than the original algorithm.Source: §2 · p. 5
- The multilevel quantity-of-interest estimator targets E[φ(X_T)] by combining many coarse-level particles with fewer fine-level particles.The aim is accuracy comparable to a single-level Monte Carlo estimator at level L, at lower cost.Source: §2 · p. 5
- The algorithm can simulate levels sequentially using stored lower-level interaction contributions, or evolve all levels simultaneously for potentially lower memory use.The simultaneous implementation is described as slightly more complicated.Source: §2 · p. 5
3 Analysis
The analysis assumes global Lipschitz bounds and a finite initial pth moment, then uses auxiliary mean-field estimates to analyze coupling and estimation errors. Its cost bound approaches O(eps^-2-delta) for any delta > 0 by taking q close to 1, at the cost of a larger constant.
3.1 Assumptions and auxiliary results
- Auxiliary mean-field particles, independent except for pairs sharing Brownian motions, provide a stepping stone for analyzing the interacting scheme's error.The analysis also uses coupled mean-field particles and a bound for level-indexed time indices.Source: §3 · p. 5, §3.1 · p. 6
- The analysis assumes global Lipschitz bounds and a finite initial moment of order p, and establishes a unique strong solution with bounded pth moments.The strong-solution result applies under Assumption 1.Source: §3.1 · p. 6
3.2 Main results
- For any delta > 0, choosing q sufficiently close to 1 gives cost O(eps^-2-delta), with an increased constant.The cost is stated for running the algorithm to a fixed time.Source: §3.2 · p. 8
- Geometric decay of the statistical error injected at each timestep is used to make summed lower-level errors dominated by the finest-level error.The proof then bounds recurrence relations by an ODE and applies Grönwall's inequality.Source: §3.2 · pp. 7, 11
- The estimator analysis separates interaction, statistical, and bias errors before bounding their sum.The stated estimator cost is O(eps^-2-4 log_a q).Source: §3.2 · pp. 8, 12, 13
4 Numerical illustration
The numerical illustration compares empirical RMSE across q values with the theoretical convergence rates for q > 1. Smaller q values perform better in this example, though they take longer to reach the asymptotic regime.
4 Numerical illustration
- The experiment uses T = 2, a = 2, ∆t0 = 0.5, CJ = 32, and 400 independent simulations per (q, L) pair.Errors are measured as RMSE against a reference solution using level L = 15 and 2 · 10^6 samples.Source: §4 · p. 13
- For q > 1, empirical errors closely track the convergence rates of the derived upper bounds.Figure 1 compares empirical RMSE with the corollary 1 rates.Source: §4 · p. 13, Figure 1 · p. 14
- q = 1 gives the best cost-error results in practice, narrowly edging out q = 1.1, although q = 1 is not covered by the theory.The experiment compares q = 1, 1.1, 1.3, and 1.5.Source: §4 · p. 13
- Smaller q values yield better convergence rates but take longer to reach the asymptotic regime.The upper-bound constant also grows as q approaches 1.Source: §4 · pp. 13–14
- At low cost, empirical errors are similar across q values, so the theory's asymptotic-versus-prefactor trade-off is absent in this example.The authors conclude that smaller q values are the clear best choice here.Source: §4 · p. 14
5 Discussion
The discussion identifies cross-level dependence as a challenge for analyzing the single-ensemble scheme and uses geometrically decreasing coarse-level errors to obtain a level-independent bound. The theory proves rates arbitrarily close to O(ϵ^-2), while its predictions do not fully capture the observed behavior near q = 1.
5 Discussion
- Cross-level dependence requires a triangle-inequality bound on multilevel estimation error, whose level-dependent accumulation would make the overall error infeasible to control through Grönwall.The authors identify this as the obstacle addressed by their proof strategy.Source: §5 · p. 14
- Requiring coarse-level coupling errors to decrease geometrically makes their sum independent of the number of levels.The method may also apply to other schemes after adapting them so particles use only lower-level particles for the interaction term.Source: §5 · pp. 14–15
- The theoretical bound permits rates arbitrarily close to O(ϵ^-2), but its exclusion of q = 1 and growing constant near 1 do not fully capture practice.The authors attribute these theory-practice gaps to a likely non-sharp triangle-inequality bound; their experiment finds performance improves as q decreases through 1.Source: §5 · p. 15
- Further work is needed on the q → 1 theory-practice gap, non-globally-Lipschitz coefficients, broader interaction terms, and comparisons among MLMC paradigms.Source: §5 · p. 15