  We present a detailed analysis of the class of regression decision tree
algorithms which employ a regulized piecewise-linear node-splitting criterion
and have regularized linear models at the leaves. From a theoretic standpoint,
based on Rademacher complexity framework, we present new high-probability upper
bounds for the generalization error for the proposed classes of regularized
regression decision tree algorithms, including LASSO-type, and $\ell_{2}$
regularization for linear models at the leaves. Theoretical result are further
extended by considering a general type of variable selection procedure.
Furthermore, in our work we demonstrate that the class of piecewise-linear
regression trees is not only numerically stable but can be made tractable via
an algorithmic implementation, presented herein, as well as with the help of
modern GPU technology. Empirically, we present results on multiple datasets
which highlight the strengths and potential pitfalls, of the proposed tree
algorithms compared to baselines which grow trees based on piecewise constant
models.
