It has been known for a long time that stratification is one possible strategy to obtain higher convergence rates for the Monte Carlo estimation of integrals over the hypercube \([0, 1]^s\) of dimension s. However, stratified estimators such as Haber’s are not practical as s grows, as they require \(\mathcal {O}(k^s)\) evaluations for some \(k\ge 2\) . We propose an adaptive stratification strategy, where the strata are derived from a decision tree applied to a preliminary sample. We show that this strategy leads to higher convergence rates, that is the corresponding estimators converge at rate \(\mathcal {O}(N^{-1/2-r})\) for some \(r>0\) for certain classes of functions. Empirically, we show through numerical experiments that the method may improve on standard Monte Carlo even when s is large.
