every tree growing algorithm, to wit the criterion used for defining the optimal split at each node, has remained relatively simple in nature and is typically based on the squared error of a piecewise constant model. The motivation behind this simplicity has invariably been linked to the tractability and numerical stability of the underlying algorithm. In the following we propose a piecewise linear splitting criterion for building a regression tree and show how modern GPU technology makes such complex criteria both tractable and numerically stable. We furthermore present a detailed theoretical analysis that provides insights into the generalization error of this model class, obtaining high probability upper bounds on the generalization error. Finally, we present empirical evidence showing that proposed algorithm consistently outperforms many benchmark algorithms which employ the aforementioned piecewise constant model criterion.

Related work {#sec:rel_work}
============

Least squares regression trees are introduced in the seminal work by Breiman et al. [@breiman1984classification]. As with the large majority of subsequent tree building algorithms, the proposed CART trees proceed in a top-down greedy manner. Nodes are split based on local criteria which in the case of regression trees takes the form of minimizing the variances of the target values in the 