PaperlayerView exact revision on arXiv

Source-linked AI summary

A Continuation Multilevel Monte Carlo algorithm

Nathan Collier, Abdul-Lateef Haji-Ali, Fabio Nobile, Erik von Schwerin, Raul Tempone

arXiv:1402.2463v3math.NAcs.NA

TL;DR

Weak approximation of stochastic models requires estimates of bias and level variances to allocate work while meeting accuracy and confidence targets. CMLMC solves a sequence of decreasing-tolerance problems using geometric hierarchies, parametric error and work models, and Bayesian estimation. The authors report an adaptive bias–statistical split, improved computational complexity and runtime variability, and computational savings in three examples.

  • Problem

    Choosing MLMC levels and sample counts requires sufficiently accurate bias and variance estimates without significant estimation overhead.

    Source: §1 · p. 2

  • Method

    CMLMC solves decreasing-tolerance problems on a priori geometric hierarchies, using parametric work and error models with Bayesian estimation.

    Source: §1 · p. 2, §4.1 · pp. 9–10, §6 · p. 19

  • Results

    The resulting estimator has a non-trivial bias–statistical split, and the authors report improved computational complexity and reduced running-time variability.

    Source: §1 · p. 3, §6 · p. 19

  • Takeaways & Limitations

    Three numerical examples demonstrate CMLMC's robustness and computational savings for differential equations driven by random measures or having random coefficients.

    Source: §6 · p. 19

    The optimality of geometric hierarchies relative to non-geometric ones is left for future work.

    Source: §6 · p. 19

Abstract

from arXiv · show

We propose a novel Continuation Multi Level Monte Carlo (CMLMC) algorithm for weak approximation of stochastic models. The CMLMC algorithm solves the given approximation problem for a sequence of decreasing tolerances, ending when the required error tolerance is satisfied. CMLMC assumes discretization hierarchies that are defined a priori for each level and are geometrically refined across levels. The actual choice of computational work across levels is based on parametric models for the average cost per sample and the corresponding weak and strong errors. These parameters are calibrated using Bayesian estimation, taking particular notice of the deepest levels of the discretization hierarchy, where only few realizations are available to produce the estimates. The resulting CMLMC estimator exhibits a non-trivial splitting between bias and statistical contributions. We also show the asymptotic normality of the statistical error in the MLMC estimator and justify in this way our error estimate that allows prescribing both required accuracy and confidence in the final result. Numerical results substantiate the above results and illustrate the corresponding computational savings in examples that are described in terms of differential equations either driven by random measures or with random coefficients.

1 Introduction

Standard MLMC reduces computational burden through a hierarchy of discretizations and level-wise sample allocation, but requires reliable bias and variance estimates and typically fixes the error split. CMLMC uses decreasing tolerances and Bayesian parameter estimation to improve those estimates and adapt the split.

1 Introduction

  • MLMC extends level-wise control variates to a hierarchy of geometrically decreasing discretizations, with optimal sample allocation reducing computational burden.The earlier method reduced the number of fine-grid samples; Giles extended this idea to a full hierarchy.Source: §1 · p. 2
  • The optimal MLMC convergence rate depends on the discretization's strong-convergence rate and the work required to generate one sample.The cited discussion notes that some cases attain the optimal rate.Source: §1 · p. 2
  • Standard MLMC needs sufficiently accurate level variances and bias estimates to achieve optimal complexity and choose the number of levels without substantial estimation overhead.Its usual variants use a fixed split between bias and statistical error.Source: §1 · p. 2
  • CMLMC uses decreasing tolerances to improve bias and variance estimates, then uses Bayesian estimation and a non-trivial bias–statistical split to improve computational complexity and reduce runtime variability.The sequence ends when the required tolerance is satisfied.Source: §1 · pp. 2–3
  • The paper outlines standard MLMC, introduces CMLMC, and presents numerical examples involving three-dimensional PDEs with random inputs and an Itô SDE.The examples are followed by conclusions and directions for future work.Source: §1 · p. 3

2 Multilevel Monte Carlo

The section formulates weak approximation as estimating an expected functional of a stochastic-model solution under accuracy and confidence requirements. It describes discretization hierarchies, level-wise estimation, work allocation, and error models for the PDE and SDE settings.

2.1 Problem Setting

  • The target is E[g(u)] for a bounded linear or Lipschitz functional, with prescribed accuracy and confidence while minimizing computational work.The discretization mesh size governs weak and strong approximation errors.Source: §2.1 · pp. 3, 5, 6
  • For finite-element PDE approximations, the weak error is bounded by QW h^2 and the variance by QS h^4 under the stated assumptions.The passage gives these asymptotic rates for piecewise linear or piecewise d-multilinear approximations.Source: §2.1 · p. 4
  • The SDE example targets E[g(u(T))] for an Itô equation and gives Euler–Maruyama weak error QW h + o(h).The example uses uniform time steps of size h.Source: §2.1 · p. 4
  • A hierarchy uses geometrically decreasing mesh sizes, and the finest-mesh expectation is represented by a telescoping sum whose terms are estimated with sample averages.The mesh sizes satisfy h_ℓ = h_0β^-ℓ for integer β > 1.Source: §2.1 · pp. 4–5
  • The work model accounts for average per-sample cost, which can vary by realization and depends on problem dimension and the numerical solver.The PDE example distinguishes iterative and direct linear-system solvers.Source: §2.1 · p. 5
  • The error budget separates bias from statistical error, with a confidence-based statistical bound motivated by the Lindeberg central limit theorem.The authors prefer this formulation because it permits prescribing both accuracy and confidence.Source: §2.1 · p. 6

3 Standard MLMC

Standard MLMC iteratively expands the discretization hierarchy and reallocates samples using estimated level variances. It estimates total error from bias and estimator variance, while commonly fixing the bias–statistical error split.

3.1 Overview

  • Standard MLMC adds levels iteratively, reuses available sample variance estimates, and commonly sets the bias–statistical error split θ to 0.5.A fixed initial sample count is generated when a level has no prior variance estimate.Source: §3.1 · p. 7
  • The section presents Standard MLMC as an overarching algorithm shared by several related variants.It notes minor variations among methods described in.Source: §3.1 · pp. 7–8
  • The bias constant QW is estimated from samples on the last two levels, so this estimate is defined only when L ≥ 2.The level variances are also used to approximate the estimator variance and total error.Source: §3.1 · p. 8

Algorithm 1

Algorithm 1 iteratively adds levels, estimates variances, allocates samples, and checks the total error against tolerance. The following analysis qualifies the accuracy of parameter estimates, especially at deep levels.

Algorithm 1

  • Each iteration adds a level, estimates its variance, computes optimal sample counts from accumulated variance estimates, runs the hierarchy, and stops when the error estimate is below TOL.The stopping check requires L ≥ 2.Source: Algorithm 1 · p. 8
  • Reusing samples from earlier iterations makes analysis of the resulting estimator's bias and statistical error difficult, and the paper notes that this analysis had not been done.The qualification concerns the usual practice of using all previously generated samples.Source: Algorithm 1 · p. 8

3.2 Accuracy of the parameter estimates

  • The relative error of the sample variance estimate can become unbounded as the level grows unless sample counts increase sufficiently fast.The passage also notes that boundedness at level zero can follow from bounded second and fourth central moments.Source: §3.2 · p. 9
  • When q2 < 2q1, obtaining a relative error estimate of o(1) for QW requires M_L ∝ β^{L(2q1−q2)} to grow as L increases.This growth is required regardless of the optimal sample-count choice in equation (2.8).Source: §3.2 · p. 9

4 Continuation MLMC (CMLMC)

CMLMC approximates E[g(u)] through progressively tighter tolerance solves, using each iteration to refine estimates of problem parameters and optimize the next hierarchy. Bayesian estimation addresses uncertain level variances and convergence parameters, including on deep levels with few samples.

4.1 Overview

  • CMLMC solves a sequence of decreasing tolerances, refining parameter estimates in relatively inexpensive problems before allocating work for the required tolerance.The tolerance sequence is chosen so total work is close to MLMC work at the desired tolerance when parameters are known in advance.Source: §4.1 · pp. 9–10
  • Each iteration selects the hierarchy depth and sample counts for its tolerance, then updates parameter estimates and the quantity of interest from new samples.The algorithm stops when its total error estimate falls below the required tolerance; the initial hierarchy has at least three levels to estimate parameters.Source: §4.1 · pp. 10–11
  • The initial hierarchy is relatively inexpensive, has at least three levels for estimating Q, and supports later parameter refinement before the required tolerance is reached.Iterations near the desired tolerance use a slightly smaller target to reduce unnecessary iterations from parameter-estimate variation.Source: §4.1 · pp. 10–11

4.2 Parameters estimation

  • For levels with too few samples, especially the deepest, Bayesian updating combines the asymptotic variance model with local sample information rather than requiring a minimum sample count.A normal-gamma prior is used for the level mean and precision, with initial guesses informed by the weak- and strong-error models.Source: §4.2.1 · pp. 11–12

4.2.2 Estimating Q

  • The weak- and strong-error parameters q1 and q2 are estimated in a Bayesian setting that incorporates q1 > 0 and q2 ≤ 2q1, using samples from levels ℓ > 0.The constraint is encoded with unconstrained log parameters, and the method uses ℓ0 = 1 for robustness.Source: §4.2.2 · pp. 12–13
  • Because the weak- and strong-error models may not hold on every level, the fitting window for QW and QS is chosen to emphasize deeper levels where their estimates affect bias and variance estimates.For QS, the fitting window uses ℓ0 = max(1, L − L̄), with L̄ a positive integer limiting the number of levels used.Source: §4.2.2 · p. 13
  • The QW estimate is made worst-case by adding a maximum sampling-error allowance at 1 − α confidence to the estimate QW*.This adjustment follows the paper's accuracy analysis of the QW estimate.Source: §4.2.2 · pp. 13–14

4.3 Algorithm parameters

  • Reasonable settings for CMLMC's control parameters produced near-optimal average running times, and reported κ1 = κ2 variations of 0.05, 0.1, and 0.2 gave similar results.The authors note that parameters may have problem-specific choices even though exact runtime-minimizing values may exist.Source: §4.3 · p. 14

Algorithm 2

Algorithm 2 initializes a hierarchy and estimates problem parameters, then repeatedly optimizes the hierarchy and sampling effort for a tolerance. It updates estimates and stops after the required error criterion is met.

Algorithm 2

  • The algorithm begins with an initial hierarchy and estimates the level variances, QS, QW, q1, and q2.These initial estimates provide inputs for choosing the subsequent hierarchy and sample counts.Source: Algorithm 2 · p. 14
  • At each iteration, it chooses the number of levels, adds any new levels, and computes optimal sample counts from variance estimates and θ.It then runs the hierarchy with those sample counts.Source: Algorithm 2 · p. 14
  • After each run, it re-estimates the problem parameters and total error, continuing until the iteration threshold and error-tolerance condition are both satisfied..Source: Algorithm 2 · p. 14

5 Numerical Tests

The tests cover two PDEs with random inputs and an Itô SDE, and report CMLMC’s runtime, accuracy, and comparison with SMLMC. CMLMC follows the expected complexity rates, achieves the prescribed accuracy with 95% confidence, and has less variable running times than SMLMC.

5.1 Test Problems

  • The test suite comprises two PDEs with random inputs and one Itô SDE; the second PDE varies the diffusion coefficient and uses independent uniform random variables.The second example is described as a slight variation of the first, with two independent uniform variables in [−1, 1] for Y, independent of Z.Source: §5.1 · p. 15, §5.1.2 · p. 16

5.2 Implementation and Runs

  • The PDE tests use PetIGA and compare GMRES with MUMPS; the reported fitted work exponents are γ̃ = 1 for GMRES and γ̃ = 1.5 for MUMPS.The PDE weak forms use a standard trilinear basis with eight quadrature points.Source: §5.2 · p. 17
  • Each algorithm is run 100 times per tolerance, and the CMLMC–SMLMC comparison assumes q1 and q2 are known for SMLMC.Results report medians with 5th-to-95th percentile bars; runs use the same machine to avoid swapping overhead.Source: §5.2 · p. 17

5.3 Results

  • CMLMC’s running time follows the expected complexity rates and matches the theoretical work complexity of the final iteration that meets the required tolerance.The reported running time includes sampling and parameter-estimation computation; the latter is largely dominated by sampling.Source: §5.3 · p. 17
  • CMLMC’s final level count depends on the realization but is well approximated by a linear function of log(TOL^-1).The level count is reported for different tolerances.Source: §5.3 · p. 18
  • CMLMC’s computational errors achieve the imposed accuracy with the required 95% confidence, and MLMC error estimates are well approximated by a standard normal CDF even at finite tolerances.SMLMC can solve below the imposed tolerance when its fixed θ does not relax statistical error as bias falls; this is especially apparent for Ex.2 with h0 = 1/8.Source: §5.3 · p. 18
  • CMLMC has less variable running times than SMLMC; SMLMC’s f_M choice trades shorter runtime for greater variation, while larger f_M increases runtime and reduces variation.The reported computational savings of CMLMC over SMLMC aggregate more stable bias and variance estimates and a better split between bias and statistical tolerances; θ changes with tolerance and can jump when the number of levels changes.Source: §5.3 · p. 18
  • Reusing samples from previous iterations does not provide significant computational savings for CMLMC, whose savings over SMLMC persist whether samples are reused or not.The paper notes that the bias of the estimator using reused samples is not well understood, while generating new samples at each iteration adds no significant overhead.Source: §5.3 · p. 19

6 Conclusions

The paper presents CMLMC for weak approximation using a priori, geometrically refined discretization hierarchies. It combines calibrated models for allocating work with Bayesian parameter estimation, and reports computational savings in three examples.

6 Conclusions

  • CMLMC uses a priori discretization hierarchies that are geometrically refined across levels.The hierarchies may be uniform at each level or formed by regular subdivision of a non-uniform mesh.Source: §6 · p. 19
  • Parametric models determine work across levels, while Bayesian estimation stabilizes weak- and strong-error parameters where deep levels have few samples.Information from coarser levels, where more samples are available, helps stabilize estimates on deeper levels.Source: §6 · p. 19
  • The bias–statistical error split depends on accuracy and problem parameters, and can devote most of the accuracy budget to statistical error.The paper also proves asymptotic normality of the MLMC statistical error, supporting error estimates with prescribed accuracy and confidence.Source: §6 · p. 19
  • Three examples demonstrate CMLMC’s robustness and computational savings for differential equations driven by random measures or having random coefficients.Source: §6 · p. 19
  • Whether geometric hierarchies are optimal relative to non-geometric ones remains an open direction for future work.Source: §6 · p. 19

A Normality of MLMC estimator

The appendix establishes conditions for the Lindeberg argument used to analyze the MLMC estimator’s statistical error. Under its stated assumptions, the relevant tail term vanishes as TOL tends to zero, with examples supplying parameter conditions.

A Normality of MLMC estimator

  • The argument assumes independent level samples and bounds on centered level errors, with positive parameters governing their decay and the level-dependent sample allocation.Source: A Normality of MLMC estimator · p. 20
  • Under the stated assumptions, either p > 0 or c < δ/p ensures that the tail term F tends to zero as TOL→0.Source: A Normality of MLMC estimator · pp. 20–21
  • The sample-allocation choice mirrors the optimal allocation for bounding statistical error by TOL, using an upper bound on level variances.Source: A Normality of MLMC estimator · p. 22
  • Examples 2.1 and 2.2 satisfy the appendix conditions with distinct parameter choices, including (q3, δ, τ)=(2, 1, 6) and (1, 2, 2), respectively.For Example 2.1, the stated conditions also assume p* > 3.Source: A Normality of MLMC estimator · p. 22
Loading 1402.2463v3…