Multilevel Monte Carlo Allocation

Allocate costly multilevel samples by variance while distinguishing real lower bounds from executable counts.

Multilevel Monte Carlo Allocation

Concept Overview

Allocate costly multilevel samples by variance while distinguishing real lower bounds from executable counts. The Multilevel Monte Carlo (MLMC) method relies on a finite telescoping estimator to approximate the expected value of a computationally expensive quantity. By distributing samples across multiple levels with different costs and variances, we can significantly reduce the overall computational cost required to achieve a target accuracy compared to standard Monte Carlo simulation.

Mathematical Definition

The MLMC estimator is based on the finite telescoping sum:

E[Q_L] = E[Q_0] + sum_(l=1)^L E[Q_l - Q_(l-1)]

Where Q_l is an approximation at level l. Assuming independent sample averages across levels with known per-sample difference variances V_l and costs C_l, the variance and total cost of the estimator for sample counts N_l are given by:

Variance = sum V_l / N_l Cost = sum C_l * N_l

The goal is to minimize the variance for a given cost budget B. The continuous optimal allocation (treating N_l as positive reals) is derived using Lagrange multipliers, which results in the unconstrained variance lower bound (sum sqrt(V_l*C_l))² / B. Since N_l must be integers greater than or equal to 1, this continuous optimum may allocate below 1 and is not an executable sample count. We find the exact bounded integer optimum through finite search, tying lexicographically by the smallest count tuple.

Worked Example

Let's consider an allocation problem using a budget B = 48 over L = 3 levels with "Fast variance" properties. The per-sample difference variances are V = [1, 1/4, 1/16], and the associated sample costs are C = [1, 2, 4].

We want to find integer sample counts [N_0, N_1, N_2] ≥ 1 that minimize the overall variance Variance = 1/N_0 + (1/4)/N_1 + (1/16)/N_2, subject to the cost budget Cost = 1*N_0 + 2*N_1 + 4*N_2 ≤ 48.

1. Calculate continuous lower bound using (sum sqrt(V_l * C_l))² / B:
   sqrt(V_0*C_0) = sqrt(1*1) = 1
   sqrt(V_1*C_1) = sqrt((1/4)*2) = sqrt(1/2) ≈ 0.707106
   sqrt(V_2*C_2) = sqrt((1/16)*4) = sqrt(1/4) = 0.5
   Sum = 1 + 0.707106 + 0.5 = 2.207106
   Variance lower bound = (2.207106)² / 48 = 4.8713... / 48 = 0.10148584049082587

2. Find best integer tuple by exhaustive search under budget 48:
   Test [22, 7, 3]: Cost = 22(1) + 7(2) + 3(4) = 22 + 14 + 12 = 48
   Variance = 1/22 + (1/4)/7 + (1/16)/3
            = 1/22 + 1/28 + 1/48
            = 0.04545... + 0.03571... + 0.02083...
            = 0.1020021645021645

The best valid integer allocation is exactly N = [22, 7, 3]. Notice that the integer variance (0.1020021645021645) is slightly strictly greater than the theoretical continuous lower bound (0.10148584049082587). A naive uniform baseline allocates floor(48 / (1+2+4)) = floor(48/7) = 6 samples to every level, giving a much worse variance of 1/6 + (1/4)/6 + (1/16)/6 = 0.21875.

Interactive Experiment

You can interactively explore the allocation algorithm using the real controls:

Adjust the Levels native select to choose between variance and cost profiles (Fast variance, Slow variance, or Expensive fine).
Modify the Level count native select to use between 1 and 3 levels. Observe how dropping levels affects the optimal counts for the remaining levels.
Change the Cost budget native select to observe how a restricted budget forces smaller sample allocations or creates large gaps between the continuous approximation and best valid integer strategy.

Open the Interactive Module to modify the controls and see the optimal allocations update in real-time.

Assumptions and Limitations

The theoretical framework of MLMC assumes several constraints that must be handled properly when implemented in real-world scenarios. The following limitations are worth considering when analyzing the generated interactive output compared to production stochastic differential equation numerical frameworks:

Discretization Bias: This module focuses purely on the statistical variance arising from the Monte Carlo sampling at the simulated levels. It explicitly ignores the structural bias (discretization error) that arises from a truncated finite level series and is not making a simulated accuracy claim.
Known Constants: We assume the variance V_l and expected cost C_l at each level are precisely known constants before allocation, whereas in real MLMC applications they are typically estimated dynamically from small sample pilots.
Continuous Relaxation: The continuous unconstrained positive real allocation allows N_l < 1, which isn't physically realizable for sample counts.
Cost Measure: Costs are represented as arbitrary normalized operations and simply scale linearly with the number of samples per level.

Primary References

To learn more about the underlying concepts, derivations, and historical development of the MLMC methodology, refer to the following scholarly resources which form the primary foundation for the calculations in this module:

Multilevel Monte Carlo Allocation