Antithetic multilevel sampling method for nonlinear functionals of measure

Łukasz Szpruch, Alvin TseThe Annals of Applied Probability 2021 · DOI

TL;DR

This paper introduces an "Antithetic Multilevel Monte Carlo" (A-MLMC) estimator for non-linear functions of probability measures. This new method offers a more efficient way to approximate complex quantities arising in statistical physics and finance, achieving sharp error bounds with reduced computational cost compared to existing techniques.

What Problem Does This Paper Address?

Estimating quantities that depend on probability measures, especially non-linear functions of these measures, is a fundamental challenge in many scientific fields. For linear functions, standard Monte Carlo methods work well. However, for non-linear functions, like those encountered in mean-field particle systems or stochastic differential equations, traditional methods become computationally prohibitive due to slow convergence rates or high variance. The paper tackles this by developing a more efficient sampling technique, specifically an "Antithetic Multilevel Monte Carlo" (A-MLMC) estimator, that can handle these complex, non-linear functionals.

Methods

The core of the paper is the development and analysis of the Antithetic Multilevel Monte Carlo (A-MLMC) estimator. This method builds upon the existing Multilevel Monte Carlo (MLMC) framework by incorporating an "antithetic" sampling strategy. MLMC works by approximating the target measure at different levels of detail, with coarser approximations being cheaper to compute. The antithetic component introduces a clever way to pair samples to reduce variance.

The paper analyzes this A-MLMC estimator in two key scenarios:

  1. Independent and Identically Distributed (i.i.d.) samples: This is the simpler case, where the estimator's performance is analyzed for general functionals.
  2. Interacting particle systems (McKean-Vlasov SDEs): This is a more complex setting, modeling systems where individual particles influence each other. The paper extends the A-MLMC approach to this scenario, including an Euler discretization for practical implementation.

A significant part of the work involves establishing theoretical guarantees for the estimator, including sharp error bounds and complexity analysis, under various regularity conditions on the functionals and the underlying dynamics.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and analysis of a sampling method, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Antithetic Sampling for Non-linear Functionals: The paper demonstrates that antithetic sampling, a technique traditionally used for variance reduction in simpler Monte Carlo settings, can be effectively extended to the more complex domain of non-linear functionals of probability measures within the MLMC framework.
  • Bridging i.i.d. and Interacting Systems: The work provides a unified approach that handles both i.i.d. samples and complex interacting particle systems, showing that the A-MLMC framework is versatile.
  • Dimension-Independent Convergence: For certain cases, the analysis reveals convergence rates that are independent of the dimensionality of the problem, which is a significant advantage for high-dimensional systems.
  • Sharp Error Bounds and Complexity: The paper establishes theoretical results that guarantee sharp error bounds for the A-MLMC estimator, and crucially, analyzes its computational complexity, showing it can be significantly more efficient than naive Monte Carlo.

Key Results

  • A-MLMC Estimator: The paper introduces and defines the A-MLMC estimator for non-linear functionals of measures.
  • Error Bounds: For i.i.d. samples, the paper establishes a dimension-independent bound on the strong error, of order $O(N^{-1/2})$, for certain classes of functionals. For interacting particle systems, they prove a dimension-independent bound in the fourth moment for strong propagation of chaos.
  • Complexity Results: The A-MLMC estimator achieves a computational cost of $O(\epsilon^{-2})$ for a mean-square error of $\epsilon^2$, which is optimal for i.i.d. samples. For interacting particle systems, the complexity is shown to be $O(\epsilon^{-2-p})$ or $O(\epsilon^{-2}(\log \epsilon)^2)$ depending on the order of interactions $p$, offering significant improvements over standard methods.
  • Time Discretization: The paper extends the A-MLMC framework to handle time-discretized stochastic differential equations, providing a practical algorithm with proven complexity bounds.

Limitations and Future Work

  • Regularity Assumptions: The theoretical guarantees of the A-MLMC estimator rely on certain regularity conditions for the functionals and the underlying stochastic processes (e.g., differentiability in measure). The paper explores these conditions but further work could investigate the performance under weaker assumptions.
  • Practical Implementation: While the paper provides a framework for implementation, especially with time discretization, further research could focus on optimizing the practical aspects of the algorithm and exploring its application to specific real-world problems.
  • Specific Functionals: The paper analyzes general classes of functionals. Future work could delve into the specific performance and advantages of A-MLMC for particular non-linear functionals that arise in specific scientific domains.

Summary updated

Abstract

Let μ∈ P2(Rd), where P2(Rd) denotes the space of square integrable probability measures, and consider a Borel-measurable function Φ:P2(Rd)→R. In this paper we develop an antithetic Monte Carlo estimator (A-MLMC) for Φ(μ), which achieves sharp error bound under mild regularity assumptions. The estimator takes as input the empirical laws μN=1N∑ i=1NδX i, where (a) (Xi)i=1N is a sequence of i.i.d. samples from μ or (b) (Xi)i=1N is a system of interacting particles (diffusions) corresponding to a McKean–Vlasov stochastic differential equation (McKV-SDE). Each case requires a separate analysis. For a mean-field particle system, we also consider the empirical law induced by its Euler discretisation which gives a fully implementable algorithm. As by-products of our analysis, we establish a dimension-independent rate of uniform strong propagation of chaos, as well as an L2 estimate of the antithetic difference for i.i.d. random variables corresponding to general functionals defined on the space of probability measures.
BibTeX
@article{szpruch2021antithetic,
  author = {Łukasz Szpruch and Alvin Tse},
  title = {{Antithetic multilevel sampling method for nonlinear functionals of measure}},
  journal = {The Annals of Applied Probability},
  year = {2021},
  doi = {10.1214/20-aap1614},
}
Figure