latter as well to the regularization constraints, which is induced by some norm on ${\mathcal{X}}$ (in particular we consider $\ell_{1}-$norm and LASSO, which is well-known for inducing the sparcity).

The paper is organized as follows: in Section \[sec:prob\_setup\_new\] we introduce the notation, present the general framework of Piecewise-Linear Regression Tree (PLRT) algorithm and provide necessary formalism to describe the model class. Section \[sec:theor\_analysis\] contains main theoretical contribution of the paper, namely the upper bound for the Rademacher complexity of the underlying regression trees class and the high probability inequality which controls the deviations of the generalization error. Futhermore, in this Section we provide the important corollaries which relate the different types of penalization (i.e. those which induce the sparsity) on the leaves to the performance of the risk bounds. Section \[sec:ctn\] is devoted to the question of numerical tractability and stability, while computing the regressor estimates on GPU, whereas Section \[sec:emp\_eval\] reports the empirical results of wide range of experiments, showing practical advantage of using GPU combined with superiority of models returned by PLRT algorithm (in comparison to well-known decision trees baselines). Finally, we conclude in Section \[sec:conc\], by highlighting the possible extensions. All the proofs can be found in 