On the effective dimension and multilevel Monte Carlo

11/05/2021

∙

by   Nabil Kahale, et al.

∙

0

∙

share

I consider the problem of integrating a function f over the d-dimensional unit cube. I describe a multilevel Monte Carlo method that estimates the integral with variance at most ϵ^2 in O(d+ln(d)d_tϵ^-2) time, for ϵ>0, where d_t is the truncation dimension of f. In contrast, the standard Monte Carlo method typically achieves such variance in O(dϵ^-2) time. A lower bound of order d+d_tϵ^-2 is described for a class of multilevel Monte Carlo methods.