Adaptive stratified Monte Carlo using decision trees

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 O(k s ) evaluations for some k ≥ 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 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.