the bound transforms to: $$\begin{aligned}
  L(f) \leq L_{n}(f) & + C_{1}W \sqrt{\frac{\ell}{{n}}} \paren{
                       {\sqrt{\frac{2\lambda}{1-\rho}} + 4C_{3}\sqrt{\lambda}\sqrt{\log{d}}\sqrt{\log{enD}}}} +C\sqrt{\frac{\log({\frac{1}{\delta}})}{2n}}.\end{aligned}$$ Here the balance between the first and second term depends on the trade-off between the log of dimensionality $d$ and the spectral decay parameter $\rho$.

### Lasso-type constraints. {#sec:lasso_type_constraints}

Consider now $B = \{f: \norm{f}_{1} \leq W \}$, where $\norm{\cdot}_{1}$ is the $\ell_{1}-$norm in the space $\mathbb{R}^{d}$. For a fixed tree $T$ and split family $\paren{i_{s},t_{s}}_{s \in T^{\circ}}$, the empirical Rademacher complexity $\hat{\mathfrak{R}}(\mathcal{F}_{T,(i_{s},t_{s})_{s\in T^{\circ}}})$ can be upper bounded as follows:

\[lem:rad\_lasso\_con\] $$\begin{aligned}
    \hat{\mathfrak{R}}_{\mathbb{S}}(\mathcal{F}_{T,(i_{s},t_{s})_{s\in T^{\circ}}}) &\leq \frac{W\sqrt{2\ell\sum_{i=1}^{n}\norm{\bx_{i}}_{\infty}^{2}}}{{n}}\paren{1+4\sqrt{\log(d)}}.
    \end{aligned}$$

Repeating the similar arguments as in the case with $\ell_{2}-$penalty we obtain: $$\begin{aligned}
    \hat{\mathfrak{R}}_{\mathbb{S}}\paren{\mathcal{F}_{T,(i_{s},t_{s})_{s\in T^{\circ}}}} = \frac{2}{n}\ee{}{\sup_{f = (f_{1},\ldots,f_{\ell})} \sum_{i=1}^{n}\epsilon_{i}f(\bx_{i})} &= \sum_{j=1}^{\ell}\frac{2}{n}\ee{}{\sup_{f_{j} \in B} \inner{f_{j},\sum_{i: \bx_{i} \in L_{j}}^{}\epsilon_{i}\bx_{i}}} \\
    & = \sum_{j=1}^{\ell}\frac{r_{j}}{n}\hat{\mathfrak{R}}_{\mathbb{S}}\paren{\hat{\mathcal{F}}_{j}},
    \end{aligned}$$ where $r_{j}=\abs{L_{j}}$ and $\hat{\mathcal{F}}_{j}$ is the empirical Rademacher complexity of class of functions, such that $\norm{f}_{1} \leq 1$ computed on the $r_{j}$ samples. Using Proposition 3 from [@maurer2012structured] with $\mathcal{P}$ being the set of orthogonal projectors on the coordinates, we obtain (recalling that $\norm{x}_{2} \leq X$, which implies that $\norm{x}_{\infty} \leq X$): $$\begin{aligned}
    \hat{\mathfrak{R}}_{\mathbb{S}}\paren{\hat{\mathcal{F}}_{j}} \leq \frac{W\sqrt{2\sum_{i: \bx_{i} \in L_{j}} \norm{\bx_{i}}^{2}_{\infty}}}{r_{j}} \paren{1+4\sqrt{\log{d}}},
    \end{aligned}$$ which implies $$\begin{aligned}
    \hat{\mathfrak{R}}_{\mathbb{S}}\paren{\mathcal{F}_{T,(i_{s},t_{s})_{s\in T^{\circ}}}} \leq \frac{2}{n}W\paren{1+4\sqrt{\log{d}}}\sum_{j=1}^{\ell}\sqrt{2\sum_{i: \bx_{i} \in L_{j}} \norm{\bx_{i}}^{2}_{\infty}} 