(R+WK)^{2}$.

Discussion of the results
-------------------------

\[rem:gen\_error\_lasso\] Notice that the second complexity term in the bound on the Rademacher complexity in Proposition \[prop:Lasso\_rad\_gen\] is the same as in the analogue result with the $\ell_{2}$ constraints. For the first complexity term, it holds $\frac{1}{n}\sum_{j=1}^{n}\norm{\bx_{j}}^{2}_{\infty} \leq \frac{1}{n}\sum_{j=1}^{n}\norm{\bx_{j}}^{2}_{2} = \tr{\hat{\Sigma}} $ and correspondingly $\ee{}{\norm{\bx}_{\infty}^{2}} \leq \tr{\Sigma}$. On the other hand, we have the additional factor of order $\sqrt{\log{d}}$ due to LASSO-type of constraints. Thus, whether LASSO-type regularization gives better bounds for generalization error in comparison to $\ell_{2}$ penalty depends on the magnitude of the ratio $r := \tr{(\Sigma)}/{\ee{}{{\norm{\bx}}_{\infty}^{2}}}$ (or its empirical counterpart $\hat{r} := \tr{(\hat{\Sigma})}/({\frac{1}{n}\sum_{j}\norm{\bx_{j}}_{\infty}^{2}})$). Namely, the LASSO-type penalty approach gives a better bound if $r$ or $\hat{r}$ are of order $\log{d}$, where $d$ is the dimensionality of the regression space. In the simple case $\Sigma=\mathbbm{I}_d$ and assuming the coordinates have subgaussian distribution, we will in fact have $\tr{\Sigma}=d$ while $\ee{}{\norm{\bx}_{\infty}^{2}} \lesssim \log(d)$.

Theoretical analysis of decision trees ( in particular regression trees) is certanly not new topic and has been considered in various settings before. For the case of $1$-dim classification, bounds for generalization error with $0/1$ loss is given in [@Mansur:99]. Furthermore, for multi-class classification the analysis of statistical performance (in 