PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Index Monte Carlo: When Sparsity Meets Sampling

Abdul-Lateef Haji-Ali, Fabio Nobile, Raul Tempone

arXiv:1405.3757v5math.NA

TL;DR

The paper addresses weak approximation of stochastic differential-equation models and PDEs with random coefficients, where MLMC-style methods can face dimensionality and regularity constraints. It introduces MIMC using high-order mixed differences and constructs optimal index sets from cost, weak-error, and variance information. Under standard assumptions, total degree index sets yield improved complexity, including dimension-independent rates up to logarithmic factors and the optimal convergence rate O(TOL^-2) over a broader parameter domain.

  • Problem

    Weak approximation of stochastic differential-equation models and PDEs with random coefficients requires methods whose complexity and conditions remain effective across multiple discretization directions.

  • Method

    MIMC combines a stochastic sparse combination technique with multidimensional indices and high-order mixed differences, selecting indices through cost, weak-error, and variance-based profits.

  • Results

    Under standard assumptions, total degree index sets are optimal, with work and memory rates independent of dimensionality up to logarithmic factors and O(TOL^-2) achievable under a broader parameter domain.

  • Takeaways & Limitations

    MIMC can provide better computational complexity than full tensor index sets and permit more accurate higher-dimensional solutions than MLMC within the stated assumptions.

  • Takeaways & Limitations

    MIMC requires mixed regularity, and it requires more regularity than MLMC; hybridizing with MLMC is proposed when regularity differs across directions.

Abstract

from arXiv · show

We propose and analyze a novel Multi-Index Monte Carlo (MIMC) method for weak approximation of stochastic models that are described in terms of differential equations either driven by random measures or with random coefficients. The MIMC method is both a stochastic version of the combination technique introduced by Zenger, Griebel and collaborators and an extension of the Multilevel Monte Carlo (MLMC) method first described by Heinrich and Giles. Inspired by Giles's seminal work, we use in MIMC high-order mixed differences instead of using first-order differences as in MLMC to reduce the variance of the hierarchical differences dramatically. This in turn yields new and improved complexity results, which are natural generalizations of Giles's MLMC analysis and which increase the domain of the problem parameters for which we achieve the optimal convergence, $\mathcal{O}(\text{TOL}^{-2}).$ Moreover, in MIMC, the rate of increase of required memory with respect to $\text{TOL}$ is independent of the number of directions up to a logarithmic term which allows far more accurate solutions to be calculated for higher dimensions than what is possible when using MLMC. We motivate the setting of MIMC by first focusing on a simple full tensor index set. We then propose a systematic construction of optimal sets of indices for MIMC based on properly defined profits that in turn depend on the average cost per sample and the corresponding weak error and variance. Under standard assumptions on the convergence rates of the weak error, variance and work per sample, the optimal index set turns out to be the total degree (TD) type. In some cases, using optimal index sets, MIMC achieves a better rate for the computational complexity than the corresponding rate when using full tensor index sets...

1. Introduction

The paper introduces Multi-Index Monte Carlo (MIMC), a stochastic sparse-combination method that generalizes MLMC through multidimensional levels and high-order mixed differences. It targets weak approximation of stochastic differential-equation models and PDEs with random coefficients, with optimal index sets and improved complexity as central goals.

  • Related work: The paper situates MIMC within prior MLMC, sparse approximation, and sparse-grid stochastic-collocation approaches, while distinguishing its stochastic combination-technique construction.Earlier work applied MLMC to SDEs, PDEs with random coefficients, jump diffusions, and sparse approximations.
  • Motivation and contribution: MIMC generalizes MLMC by replacing one-dimensional levels and first-order differences with multidimensional levels and high-order mixed differences.The construction is presented as a stochastic version of a sparse combination technique.
  • Motivation and contribution: High-order mixed differences reduce hierarchical-difference variance and support the target Monte Carlo complexity O(TOL^-2).The paper frames this as an improved complexity result relative to standard MLMC analysis.
  • Index sets: The method analyzes both full tensor and total degree index sets, with total degree sets shown to be optimal under stated assumptions.The paper develops full tensor estimates as motivation before establishing the total degree result.
  • Problem setting: MIMC addresses weak approximation for stochastic models described by differential equations driven by random measures or having random coefficients.The problem setting includes stochastic differential equations and PDEs with random coefficients.
  • Problem setting: For a discretized quantity S_alpha, MIMC organizes approximations using multidimensional integer indices and convergence of E[S_alpha] toward E[S].The discretization vector h controls the weak error and variance, while alpha indexes the discrete approximations.

2. Multi-Index Monte Carlo

MIMC combines mixed differences across multiple discretization directions with Monte Carlo sampling, then selects index sets using error, variance, and work estimates. Under Assumptions 1–3, optimal total-degree sets yield improved complexity and dimension-robust memory behavior, while requiring mixed regularity.

  • MIMC construction: MIMC recursively combines first-order differences across all discretization directions to form mixed differences.A mixed difference generally requires 2^d evaluations of the functional at different discretization parameters.
  • MIMC construction: The MIMC estimator averages independent unbiased mixed-difference samples over an index set, with sample counts chosen per multi-index.Its work and variance depend on each multi-index’s variance V_α and average work W_α.
  • Assumptions: The analysis assumes directional convergence rates for the mixed-difference bias, variance, and work per sample.Assumptions 1–3 characterize these quantities through positive constants and directional rates w_i, s_i, and γ_i.
  • Optimal index sets: Optimal profit sets minimize error for a given work budget by retaining indices whose profit exceeds a threshold.The profit construction uses the estimated weak error, variance, and work associated with each multi-index.
  • Optimal index sets: Under the stated assumptions, selecting optimal weights produces anisotropic total-degree index sets and the work estimates in Theorem 2.2.Theorem 2.2 specializes the general-weight result to the optimal weights and provides case-dependent complexity rates.
  • Complexity and limitations: For multi-directional problems with variance convergence slower than work growth, MIMC can outperform MLMC, while optimal total-degree sets make the complexity rate dimension-independent up to logarithmic factors.The total-degree condition is less restrictive than the full-tensor condition in the isotropic case, but MIMC requires mixed regularity.

3. Numerical Example

The numerical example compares MLMC, full-tensor MIMC, and total-degree MIMC for a three-dimensional random-coefficient PDE, using increasingly accurate tolerance targets. The results are consistent with the theoretical convergence rates and favor total-degree index sets for computational complexity.

  • Experimental setup: The experiment compares MLMC, full-tensor MIMC, and isotropic total-degree MIMC on the same three-dimensional problem.The total-degree method is denoted “TD” and the full-tensor method “FT” in the figures.
  • Experimental setup: The model uses a random-coefficient PDE on D = [0, 1]3 with a two-variable diffusion coefficient and quantity of interest S.A stochastic-collocation reference value of 1.3301 was computed with an error estimate of 10^-4.
  • Solvers and algorithms: Uniform Cartesian meshes with trilinear finite elements produce an isotropic discretization with wi = 2 and si = 4 in all three dimensions.The MUMPS solver’s running time ranges from quadratic to linear in total degrees of freedom, giving γi values from 1 to 2.
  • MIMC algorithm: MIMC estimates sample counts from sample variances, enforces at least M0 = 5 samples per level, and uses fixed tolerance splitting θ = 0.5.The algorithm iteratively expands the index set until its bias estimate is below (1 − θ)TOL.
  • MIMC algorithm: The bias indicator is used heuristically because it does not generally provide an error bound without additional assumptions on the integrand.Its expectations are approximated by sample averages over the available boundary-index samples.
  • Results: For the example’s parameters, the optimal TD index set satisfies the MIMC condition, whereas the full-tensor condition fails for γ ∈ [1, 2].The reported numerical results agree with the predicted rates s = 4 and w = 2, and the TD method is expected to have the favorable complexity rate when γ is near 2.
  • Results: In four dimensions, the expected TD-MIMC work rate remains O while the MLMC rate is reported separately for comparison.The memory limit restricted the MLMC tolerances that could be computed to those feasible with 64 gigabytes.

4. Conclusions

MIMC combines stochastic combination techniques with high-order mixed differences and optimized index sets to improve complexity, memory scaling, and attainable accuracy over MLMC in supported settings.

  • Method: MIMC generalizes MLMC by using multi indices and high-order mixed differences in a stochastic combination technique.The method targets weak approximation for stochastic differential-equation models driven by random measures or having random coefficients.
  • Numerical evidence: Numerical experiments support the predicted convergence rates, with MIMC mixed differences outperforming MLMC differences in the reported example.The experiments also show behavior consistent with the stated assumptions and rate models.
  • Index sets: Under standard assumptions, total degree index sets are optimal and yield better computational-complexity rates than full tensor index sets.The resulting rate is independent of problem dimensionality up to logarithmic factors.
  • Computational complexity: MIMC with total degree index sets exhibits the expected optimal Monte Carlo work rate of O(TOL^-2) in the numerical example.The reported comparison indicates MLMC is closer to a less favorable rate for the stated three-dimensional parameter setting.
  • Scope and future work: MIMC requires more regularity of the underlying solution than MLMC, although mixed MLMC/MIMC differences can address directionally uneven regularity.The authors also identify variance estimation and tolerance splitting as areas for algorithmic improvement.
  • Memory: Total degree index sets achieve the same tolerance with substantially fewer degrees of freedom than the compared MLMC and MIMC index sets.This supports the reported memory advantage of total degree constructions.

Appendix A. Asymptotic Normality of the MIMC estimator

Appendix A establishes asymptotic normality for the MIMC estimator under conditions on level growth, sample allocation, and convergence parameters, using a Lindeberg-condition argument.

  • Estimator and assumptions: The appendix analyzes the MIMC estimator over a set of multi-indices and specifies level-dependent sample numbers Mα(TOL).The construction uses strictly positive sequences and conditions on the quantities Li(TOL), ci, and pi.
  • Proof strategy: The proof establishes the estimator’s asymptotic normality by verifying the Lindeberg condition.The argument repeatedly applies bounds, Markov’s inequality, and the variance representation of the hierarchical differences.
  • Index classification: The index directions are partitioned according to whether pi is negative, zero, or positive.The sets are denoted Î1, Î2, and Î3, respectively.
  • Asymptotic conclusion: The appendix concludes that the auxiliary quantity F tends to zero as TOL decreases, both when Î3 is empty and when it is nonempty under cipi < ρ.The conclusion applies for any nonnegative Li in the first case and under the stated inequality in the second.
  • Allocation and bias: The lower bound on samples per index mirrors the optimal allocation satisfying the sampling constraint, with Hα = √VαWα and s̃i = si.The appendix also distinguishes upper bounds on L from lower bounds needed to satisfy the bias constraint.

Appendix B. Integrating an exponential over a simplex

Appendix B develops identities and bounds for integrating exponentials over a simplex, including cases determined by the largest component of a vector and its multiplicity.

  • Integral identities: The appendix introduces identities for simplex integrals involving exponential terms and factorial expressions.These identities are used repeatedly in subsequent bounds.
  • Proof strategy: The proof proceeds by induction on the dimension d and repeatedly applies the simplex-integral identity.The induction step assumes the identity for d − 1 before proving it for d.
  • Case structure: For a vector a, the largest component A and its multiplicity a1 determine the complementary count a2 = d − a1.The appendix explicitly defines a1 as the number of components equal to A.
  • Bounds: The resulting bounds hold for positive L and include a constant CW(a) specified by the appendix.The bound is stated after introducing an ε satisfying the required inequality.
  • Resulting estimate: A derived estimate bounds the expression by 4C ε(2A − ε) exp(AL) L^(a1−1).The constant C is defined using exp(1 − a2) and factorial terms.

Appendix C. List of Definitions

Appendix C collects notation used across the work and points to the equations or pages where the symbols are defined.

  • Purpose: The appendix states that it lists notation appearing across multiple pages or sections.Its purpose is cross-reference rather than introducing a new analytical result.
  • Core notation: The notation list includes tolerances, error terms, index sets, convergence parameters, and cost quantities from equations 8 through 28.Examples include TOLS, TOLB, I, I1, I2, I3, Î, si, wi, and γi.
  • Later notation: Later entries cover parameters and constants from equations 34 through 63, including χ, η, γ, ζ, ξ, CBias, CA, CR, IC, ID, pi, and CW.The list preserves the equation references for these symbols.
Loading 1405.3757v5…