criterion. Two such approaches [@GUIDE; @SUPPORT] use the residuals of a linear regressor at each node to perform a kind of clustering, while another approach [@vogel07scalable] replaces linear regression with forward selection regression at each node in order to reduce the dimensionality of the models.

We mention here, for the sake of completeness, that though greedy top-down growing of trees is the most common approach, there exist other approaches, such as so-called “soft” trees [@chipman2010] which predefine the tree architecture and then optimize, in a global manner, the split functions. Other non-greedy strategies for learning the split criteria have also been studied in the literature, as for example via multi-linear programming [@benett1994global] and structured prediction [@norouzi2015efficient].

We focus however on the specific, sometimes called “hard”, family of tree algorithms. We show in the following that despite the increased computational cost of using the criterion in Equation , modern GPU technology ensures that this approach is both tractable and numerically stable. More importantly we provide a comprehensive theoretical analysis of this model class, by separating the “split” space $\mathbf{\mathcal{X}^{'}}$ from the “regression” space ${\mathcal{X}}$ we show that the generalization capabilities of the model class are linked to the dimensionality of the 