= \ee{}{\bx \bx^{\top}}$ the covariance matrix of the random vector $\bx$, and $\hat{\Sigma} = \frac{1}{n} \sum_{i=1}^n \bx_i\bx_i^t$ its empirical counterpart.

### Euclidean-norm penalty.

Let $B = \{ \norm{f}_{2} \leq W \}$. Recall that our goal is now to control $\max_{T,(i_{s},t_{s})_{s \in T^{\circ}}} \hat{\mathfrak{R}}_{\mathbb{S}}(\mathcal{F}_{T,(i_{s},t_{s})_{s\in T^{\circ}}})$ for decision trees of total number of leaves $\ell$. The following result holds true.

\[eq:l2\_bound\] For a fixed tree structure $T$ with $\ell$ leaves and the splits $(i_{s},t_{s})_{s \in T^{\circ}}$ we have the following upper bounds: $$\begin{aligned}
        \hat{\mathfrak{R}}_{\mathbb{S}}\paren{\mathcal{F}_{T,(i_{s},t_{s})_{s\in T^{\circ}}}} &\leq \frac{W\sqrt{2\ell} \sqrt{\sum_{j}\norm{\bx_{j}}_{2}^{2}}}{n} =  W\sqrt{\frac{2 \ell \tr{\hat{\Sigma}}}{n}};\\
        {\mathfrak{R}}_{n}\paren{\mathcal{F}_{T,(i_{s},t_{s})_{s\in T^{\circ}}}} &\leq  W\sqrt{\frac{{2\ell \tr{{\Sigma}}}}{n}}.
    \end{aligned}$$

Notice that the upper bound for the empirical Rademacher complexity is data-dependent, but does not depend on the structure of the decision tree with fixed splits.

\[lem:rademacher\_ell2\] By linearity of expectation and taking into account that leaves $(L_{j})_{j=1}^{\ell}$ are disjoint sets we obtain: $$\begin{aligned}
    \ee{}{\sup_{f = (f_{1},\ldots,f_{\ell})} \sum_{i=1}^{n}\epsilon_{i}f(\bx_{i})} &= \sum_{j=1}^{\ell}\ee{}{\sup_{f_{j} \in B} \inner{f_{j},\sum_{i: \bx_{i} \in L_{j}}^{}\epsilon_{i}\bx_{i}}} \\
    & \leq W \sum_{j=1}^{\ell} \ee{}{\norm[2]{\sum_{i: \bx_{i} \in L_{j}}^{}\epsilon_{i}\bx_{i}}_{2}} \\
    & \leq W\sum_{j=1}^{\ell}\sqrt{\ee{}{\sum_{i,k: \bx_{i},\bx_{k} \in L_{j}}^{}\epsilon_{i}\epsilon_{k}\inner{\bx_{i},\bx_{k}}}},
    \end{aligned}$$ where we used Jensen’s inequality in the last line. Since $(\epsilon_{i})_{i=1}^{n}$ are independent Rademacher variables, by taking expectation, we obtain: $$\begin{aligned}
    \ee{}{\sup_{f = (f_{1},\ldots,f_{\ell})} \sum_{i=1}^{n}\epsilon_{i}f(\bx_{i})} \leq W \sum_{j=1}^{\ell}\sqrt{\sum_{i: \bx_{i} \in L_{j}}\norm{\bx_{i}}^{2}} 