Abstract
This paper shows that decision trees constructed with Classification andRegression Trees (CART) methodology are universally consistent for additivemodels, even when the dimensionality scales exponentially with the sample size,under certain $\ell_1$ sparsity constraints. The consistency is universal inthe sense that there are no a priori assumptions on the distribution of theinput variables. Surprisingly, this adaptivity to (approximate or exact)sparsity is achieved with a single tree, as opposed to what might be expectedfor an ensemble. Finally, we show that these qualitative properties ofindividual trees are inherited by Breiman's random forests. A key step in theanalysis is the establishment of an oracle inequality, which preciselycharacterizes the goodness-of-fit and complexity tradeoff.