Multi-level Monte Carlo

This tutorial builds upon Two model Approximate Control Variate Monte Carlo and describes how the pioneering work of Multi-level Monte Carlo (MLMC) [CGSTCVS2011], [GOR2008] can be used to estimate the mean of a high-fidelity model using multiple low fidelity models. MLMC is actually a special type of ACV estimator, but it was not originally derived this way. Consequently, this tutorial begins by presenting the typical formulation of MLMC and then concludes by discussing relationships with ACV.

Two Model MLMC

The two model MLMC estimator is based upon the observations that we can estimate

$$\mathbb{E}\left[f_0\right]=\mathbb{E}\left[f_1\right]+\mathbb{E}[f_0-f_1]$$

using the following unbiased estimator

$$Q_0^{\mathrm{ML}}({\mathcal{Z}}_0,{\mathcal{Z}}_1)=N_1^{-1}\sum _{i=1}^{N_1}{f}_1^{(i)}({\mathcal{Z}}_1)+N_0^{-1}\sum _{i=1}^{N_0}(f_0^{(i)}({\mathcal{Z}}_0)-f_1^{(i)}({\mathcal{Z}}_0)),$$

where $f_{\alpha }^{(i)}({\mathcal{Z}}_{\kappa })$ denotes an evaluation of $f_{\alpha }$ using a sample from the set ${\mathcal{Z}}_{\kappa }$. To evaluate this estimator we must evaluate the low fidelity model at a set of samples ${\mathcal{Z}}_1$ and then evaluate the difference between the two models at another independet set ${\mathcal{Z}}_0$.

To simplify notation let

$$Y_{\alpha }({\mathcal{Z}}_{\alpha })=-N_{\alpha }^{-1}\sum _{i=1}^{N_{\alpha }}(f_{\alpha +1}^{(i)}({\mathcal{Z}}_{\alpha })-f_{\alpha }^{(i)}({\mathcal{Z}}_{\alpha }))$$

so we can write

$$Q_0^{\mathrm{ML}}({\mathcal{Z}}_0,{\mathcal{Z}}_1)=Y_0({\mathcal{Z}}_0)+Y_1({\mathcal{Z}}_1)$$

where $f_2=0$.

Now it is easy to see that the variance of this estimator is given by

$$\mathbb{V}[Q_0^{\mathrm{ML}}({\mathcal{Z}}_0,{\mathcal{Z}}_1)]=\mathbb{V}[Y_0({\mathcal{Z}}_0)+Y_1({\mathcal{Z}}_1)]=N_0^{-1}\mathbb{V}[Y_0({\mathcal{Z}}_0)]+N_1^{-1}\mathbb{V}[Y_1({\mathcal{Z}}_1)]$$

where $N_{\alpha }=|{\mathcal{Z}}_{\alpha }|$ and we used the fact

${\mathcal{Z}}_0\bigcap {\mathcal{Z}}_1=\mathrm{\varnothing }$ so $\mathbb{C}\text{ov}[Y_0({\mathcal{Z}}_0),Y_0({\mathcal{Z}}_1)]=0$

From the previous equation we can see that MLMC works well if the variance of the difference between models is smaller than the variance of either model. Although the variance of the low-fidelity model is likely high, we can set $N_0$ to be large because the cost of evaluating the low-fidelity model is low. If the variance of the discrepancy is smaller we only need a smaller number of samples so that the two sources of error (the two terms on the RHS of the previous equation) are balanced.

Note above and below we assume that $f_0$ is the high-fidelity model, but typical multi-level literature assumes $f_M$ is the high-fidelity model. We adopt the reverse ordering to be consistent with control variate estimator literature.

Many Model MLMC

MLMC can easily be extended to estimator based on $M+1$ models. Letting $f_0,\dots ,f_M$ be an ensemble of $M+1$ models ordered by decreasing fidelity and cost (note typically MLMC literature reverses this order), we simply introduce estimates of the differences between the remaining models. That is

(1)$$Q_0^{\mathrm{ML}}(\mathcal{Z})=\sum _{\alpha =0}^M{Y}_{\alpha }({\mathcal{Z}}_{\alpha }),f_{M+1}=0$$

To compute this estimator we use the following algorithm, starting with $\alpha =M$

1. Draw $N_{\alpha }$ samples randomly from the PDF $\rho$ of the random variables.

2. Estimate $f_{\alpha }$ and $f_{\alpha }$ at the samples ${\mathcal{Z}}_{\alpha }$

3. Compute the discrepancies $Y_{\alpha ,{\mathcal{Z}}_{\alpha }}$ at each sample.

4. Decrease $\alpha$ and repeat steps 1-3. until $\alpha =0$.

5. Compute the ML estimator using (1)

In the above algorithm, we evaluate only the lowest fidelity model with ${\mathcal{Z}}_M$ (this follows from the assumption that $f_{M+1}=0$) and evaluate each discrepancies between each pair of consecutive models at the sets ${\mathcal{Z}}_{\alpha }$, such that ${\mathcal{Z}}_{\alpha }\cap {\mathcal{Z}}_{\beta }=\mathrm{\varnothing },\alpha \ne \beta$ and the variance of the MLMC estimator is

$$\mathbb{V}[Q_0^{\mathrm{ML}}({\mathcal{Z}}_0,\dots ,{\mathcal{Z}}_M)]=\sum _{\alpha =0}^M{N}_{\alpha }\mathbb{V}[Y_{\alpha }({\mathcal{Z}}_{\alpha })]$$

Optimal Sample Allocation

When estimating the mean, the optimal allocation can be determined analytically. The following follows closely the exposition in [GAN2015] to derive the optimal allocation.

Let $C_{\alpha }$ be the cost of evaluating the function $f_{\alpha }$ at a single sample, then the total cost of the MLMC estimator is

$$C_{\mathrm{tot}}=\sum _{\alpha =0}^M{C}_{\alpha }{N}_{\alpha }$$

Now recall that the variance of the estimator is

$$\mathbb{V}\left[Q_0^{\mathrm{ML}}\right]=\sum _{\alpha =0}^M\mathbb{V}\left[Y_{\alpha }\right]N_{\alpha },$$

where $Y_{\alpha }$ is the disrepancy between two consecutive models, e.g. $f_{\alpha -1}-f_{\alpha }$ and $N_{\alpha }$ be the number of samples allocated to resolving the discrepancy, i.e. $N_{\alpha }=|{\hat{\mathcal{Z}}}_{\alpha }|$. Then For a fixed variance ${ϵ}^2$ the cost of the MLMC estimator can be minimized, by solving

$$\begin{array}{rl}\underset{N_0,\dots ,N_M}{min}& \sum _{\alpha =0}^M\left(N_{\alpha }{C}_{\alpha }\right)\\ \mathrm{subject}\mathrm{to}& \sum _{\alpha =0}^M\left(N_{\alpha }^{-1}\mathbb{V}\left[Y_{\alpha }\right]\right)={ϵ}^2\end{array}$$

or alternatively by introducing the lagrange multiplier ${\lambda }^2$ we can minimize

$$\begin{array}{rl}\mathcal{J}(N_0,\dots ,N_M,\lambda )& =\sum _{\alpha =0}^M\left(N_{\alpha }{C}_{\alpha }\right)+{\lambda }^2(\sum _{\alpha =0}^M\left(N_{\alpha }^{-1}\mathbb{V}\left[Y_{\alpha }\right]\right)-{ϵ}^2)\\ & =\sum _{\alpha =0}^M(N_{\alpha }{C}_{\alpha }+{\lambda }^2{N}_{\alpha }^{-1}\mathbb{V}\left[Y_{\alpha }\right])-{\lambda }^2{ϵ}^2\end{array}$$

To find the minimum we set the gradient of this expression to zero:

$$\begin{array}{rl}\frac{\partial {\mathcal{J}}^{\mathrm{ML}}}{N_{\alpha }}& =C_{\alpha }-{\lambda }^2{N}_{\alpha }^{-2}\mathbb{V}\left[Y_{\alpha }\right]=0\\ ⟹C_{\alpha }& ={\lambda }^2{N}_{\alpha }^{-2}\mathbb{V}\left[Y_{\alpha }\right]\\ ⟹N_{\alpha }& =\lambda \sqrt{\mathbb{V}\left[Y_{\alpha }\right]C_{\alpha }^{-1}}\end{array}$$

The constraint is satisifed by noting

$$\frac{\partial \mathcal{J}}{{\lambda }^2}=\sum _{\alpha =0}^M{N}_{\alpha }^{-1}\mathbb{V}\left[Y_{\alpha }\right]-{ϵ}^2=0$$

Recalling that we can write the total variance as

$$\begin{array}{rl}\mathbb{V}\left[Q_{0,\mathcal{Z}}^{\mathrm{ML}}\right]& =\sum _{\alpha =0}^M{N}_{\alpha }^{-1}\mathbb{V}\left[Y_{\alpha }\right]\\ & =\sum _{\alpha =0}^M{\lambda }^{-1}{\mathbb{V}\left[Y_{\alpha }\right]}^{-\frac{1}{2}}{C}_{\alpha }^{\frac{1}{2}}\mathbb{V}\left[Y_{\alpha }\right]\\ & ={\lambda }^{-1}\sum _{\alpha =0}^M\sqrt{\mathbb{V}\left[Y_{\alpha }\right]C_{\alpha }}={ϵ}^2\\ ⟹\lambda & ={ϵ}^{-2}\sum _{\alpha =0}^M\sqrt{\mathbb{V}\left[Y_{\alpha }\right]C_{\alpha }}\end{array}$$

Then substituting $\lambda$ into the following

$$\begin{array}{rl}{N}_{\alpha }{C}_{\alpha }& =\lambda \sqrt{\mathbb{V}\left[Y_{\alpha }\right]C_{\alpha }^{-1}}{C}_{\alpha }\\ & =\lambda \sqrt{\mathbb{V}\left[Y_{\alpha }\right]C_{\alpha }}\\ & ={ϵ}^{-2}\left(\sum _{\alpha =0}^M\sqrt{\mathbb{V}\left[Y_{\alpha }\right]C_{\alpha }}\right)\sqrt{\mathbb{V}\left[Y_{\alpha }\right]C_{\alpha }}\end{array}$$

allows us to determine the smallest total cost that generates and estimator with the desired variance.

$$\begin{array}{rl}{C}_{\mathrm{tot}}& =\sum _{\alpha =0}^M{N}_{\alpha }{C}_{\alpha }\\ & =\sum _{\alpha =0}^M{ϵ}^{-2}\left(\sum _{\alpha =0}^M\sqrt{\mathbb{V}\left[Y_{\alpha }\right]C_{\alpha }}\right)\sqrt{\mathbb{V}\left[Y_{\alpha }\right]C_{\alpha }}\\ & ={ϵ}^{-2}{\left(\sum _{\alpha =0}^M\sqrt{\mathbb{V}\left[Y_{\alpha }\right]C_{\alpha }}\right)}^2\end{array}$$

Lets setup a problem to compute an MLMC estimate of $\mathbb{E}\left[f_0\right]$ using the following ensemble of models

$$f_{\alpha }(z)=z^{5-\alpha },\alpha =0,\dots ,4$$

where $z\sim \mathcal{U}[0,1]$

First load the necessary modules

import numpy as np
import matplotlib.pyplot as plt

from pyapprox.util.visualization import mathrm_labels
from pyapprox.benchmarks import setup_benchmark
from pyapprox.multifidelity.factory import (
    get_estimator, compare_estimator_variances, multioutput_stats)
from pyapprox.multifidelity.visualize import (
    plot_estimator_variance_reductions, plot_estimator_variances,
    plot_estimator_sample_allocation_comparison)

The following code computes the variance of the MLMC estimator for different target costs using the optimal sample allocation using an exact estimate of the covariance between models and an approximation.

np.random.seed(1)
benchmark = setup_benchmark("polynomial_ensemble")
poly_model = benchmark.fun
cov = benchmark.covariance
target_costs = np.array([1e1, 1e2, 1e3], dtype=int)
costs = np.asarray([10**-ii for ii in range(cov.shape[0])])
model_labels = [r'$f_0$', r'$f_1$', r'$f_2$', r'$f_3$', r'$f_4$']
stat = multioutput_stats["mean"](benchmark.nqoi)
stat.set_pilot_quantities(cov)
estimators = [
    get_estimator("mc", stat, costs),
    get_estimator("mlmc", stat, costs)]
est_labels = mathrm_labels(["MC", "MLMC"])
optimized_estimators = compare_estimator_variances(
    target_costs, estimators)

The following compares the estimator variance reduction ratio of MLMC relative to MLMC for a fixed target cost

axs = [plt.subplots(1, 1, figsize=(8, 6))[1]]
# get estimators for target cost = 100
mlmc_est_100 = optimized_estimators[1][1:2]
_ = plot_estimator_variance_reductions(
    mlmc_est_100, est_labels[1:2], axs[0])

The following compares the estimator variance of MC with MLMC for a set of target costs and plot the number of samples allocated to each model by MLMC

# get MLMC estimators for all target costs
mlmc_ests = optimized_estimators[1]
axs[0].set_xlim(target_costs.min(), target_costs.max())
fig, axs = plt.subplots(1, 2, figsize=(2*8, 6))
plot_estimator_sample_allocation_comparison(
    mlmc_ests, model_labels, axs[0])
_ = plot_estimator_variances(
    optimized_estimators, est_labels, axs[1],
    relative_id=0, cost_normalization=1)

The left plot shows that the variance of the MLMC estimator is over and order of magnitude smaller than the variance of the single fidelity MC estimator for a fixed cost. The impact of using the approximate covariance is more significant for small samples sizes.

The right plot depicts the percentage of the computational cost due to evaluating each model. The numbers in the bars represent the number of samples allocated to each model. Relative to the low fidelity models only a small number of samples are allocated to the high-fidelity model, however evaluating these samples represents approximately 50% of the total cost.

Multi-index Monte Carlo

Multi-Level Monte Carlo utilizes a sequence of models controlled by a single hyper-parameter, specifying the level of discretization for example, in a manner that balances computational cost with increasing accuracy. In many applications, however, multiple hyper-parameters may control the model discretization, such as the mesh and time step sizes. In these situations, it may not be clear how to construct a one-dimensional hierarchy represented by a scalar hyper-parameter. To overcome this limitation, a generalization of multi-level Monte Carlo, referred to as multi-index stochastic collocation (MIMC), was developed to deal with multivariate hierarchies with multiple refinement hyper-parameters [HNTNM2016]. PyApprox does not implement MIMC but a surrogate based version called Multi-index stochastic collocation (MISC) is presented in this tutorial Multi-level and Multi-index Collocation.

The Relationship between MLMC and ACV

MLMC estimators can be thought of a specific case of an ACV estimator. When using two models this can be seen by

$$\begin{array}{rl}{Q}_0^{\mathrm{ML}}({\mathcal{Z}}_0,{\mathcal{Z}}_1)& =Y_0({\mathcal{Z}}_0)+Y_1({\mathcal{Z}}_1)\\ & =Q_0({\mathcal{Z}}_0)-Q_1({\mathcal{Z}}_0)+Q_1({\mathcal{Z}}_1)\\ & =Q_0({\mathcal{Z}}_0)-(Q_1({\mathcal{Z}}_0)-Q_1({\mathcal{Z}}_1))\end{array}$$

which has the same form as the two model ACV estimator presented in Two model Approximate Control Variate Monte Carlo where the control variate weight has been set to $-1$.

For three models the allocation matrix of MLMC is

$$\begin{array}{r}\mathbf{A}=\left[\begin{array}{cccccccc}0& 1& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 0& 0& 0& 1\end{array}\right]\end{array}$$

The following code plots the allocation matrix of one of the 5-model estimator we have already optimized. The numbers inside the boxes represent the sizes $p_m$ of the independent partitions (different colors).

import matplotlib as mpl
params = {'xtick.labelsize': 24,
          'ytick.labelsize': 24,
          'font.size': 18}
mpl.rcParams.update(params)
ax = plt.subplots(1, 1, figsize=(8, 6))[1]
_ = mlmc_ests[0].plot_allocation(ax, True)

MLMC was designed when it is possible to always able to create new models with smaller bias than those already being used. Such a situation may occur, when refining the mesh of a finite element discretization. However, ACV methods were designed where there is one trusted high-fidelity model and unbiased statistics of that model are required. In the setting targeted by MLMC, the properties of MLMC can be used to bound the work needed to achieve a certain MSE if theoretical estimates of bias convergence rates are available. Such results are not possible with ACV.

The following code builds an MLMC estimator with the optimal control variate weights and compares them to traditional MLMC when estimating a single mean.

estimators = [
    get_estimator("mc", stat, costs),
    get_estimator("mlmc", stat, costs),
    get_estimator("grd", stat, costs,
                  recursion_index=range(len(costs)-1))]
est_labels = mathrm_labels(["MC", "MLMC", "MLMC-OPT"])
optimized_estimators = compare_estimator_variances(
    target_costs, estimators)

axs = [plt.subplots(1, 1, figsize=(8, 6))[1]]

# get estimators for target cost = 100
mlmc_est_100 = [optimized_estimators[1][1], optimized_estimators[2][1]]
_ = plot_estimator_variance_reductions(
    mlmc_est_100, est_labels[1:3], axs[0])

For this problem there is a substantial difference between the two types of MLMC estimators.

Remark

MLMC was originally developed to estimate the mean of a function, but adaptations MMLC have since ben developed to estimate other statistics, e.g. [MD2019]. PyApprox, however, does not implement these specific methods, because it implements a more flexible way to compute multiple statistics which we will describe in later tutorials.

Video

Click on the image below to view a video tutorial on multi-level Monte Carlo quadrature

References

[CGSTCVS2011]

K.A. Cliffe, M.B. Giles, R. Scheichl, A.L. Teckentrup, Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients, Comput. Vis. Sci., 14, 3-15, 2011.

[GOR2008]

M.B. Giles, Multilevel Monte Carlo path simulation, Oper. Res., 56(3), 607-617, 2008.

[GAN2015]

M. Giles, Multilevel Monte Carlo methods, Acta Numerica, 24, 259-328, 2015.

[HNTNM2016]

A. Haji-Ali, F. Nobile and R. Tempone. Multi-index Monte Carlo: when sparsity meets sampling. Numerische Mathematik, 132(4), 767-806, 2016.

[MD2019]

P. Mycek, M. De Lozzo. Multilevel Monte Carlo Covariance Estimation for the Computation of Sobol’ Indices. 2019.