Minimax optimal rates for Mondrian trees and forests (Q2215734)

The main contribution of this article is two-fold. First, the consistency and convergence rates for Mondrian trees and forests with control of the cells diameter and distribution are derived. Second, it is demonstrated that such particular random forests achieve minimax rates in arbitrary dimension. This is the first contribution to the theory of the random forest method in arbitrary dimension. It is to be noted that the minimax rate \(O(n^{-2s/(2s+d)})\) for the \(s\)-Hölder regression \(s\in (0,2]\) is slow for large number of features and it is interesting to study the random forest algorithms taking into account the sparsity assumption.