classical argument we can reduce it to a finite union when considering the empirical Rademacher complexity.

First bound we obtain by a simple upper bounding of the number of the possible splits ($((n-1)D)^{\ell-1}$) in the tree and the number of different trees with $\ell$ leaves (which is the $\ell-1$ Catalan’s number). Futhermore, by using simple inequalities $(\frac{k}{e})^k<k!<e(\frac{k}{2})^k$ we obtain $\frac{1}{\ell} \binom{2(\ell-1)}{\ell-1}  \leq \frac{e^{\ell}}{\ell}$ and the second claim follows by simple calculations.

\[lem: help\_lem01\] $$\begin{aligned}
          \hat{\mathfrak{R}}_{\mathbb{S}} \paren{\mathcal{F}}
          = \hat{\mathfrak{R}}_{\mathbb{S}} \paren[4]{\bigcup_{\substack{T \in \cT_l\\(i_s,t_s)_{s} \in ([D] \times [n])^{T^\circ}}} \mathcal{F}_{T,(i_{s},\psi_{k_s}^{i_s})_{s\in T^{\circ}}}}
          &\leq \max_{T,\paren{i_{s},t_{s}}_{s \in T^{\circ}}}\hat{\mathfrak{R}}_{\mathbb{S}}(\mathcal{F}_{T,\paren{i_{s},t_{s}}_{s \in T^{\circ}}}) + 4\mathcal{M}\sqrt{\frac{\ell\log{enD}}{n}}, \\
    \end{aligned}$$ where $\mathcal{M} = \sqrt{\sup\limits_{f \in \cF}\frac{1}{n}\sum_{i=1}^{n}f^{2}(\bx_{i})}$.

With the notation as in Section \[sec:prob\_setup\_new\] we obtain:

\[thm:main\_theorem01\] With probability at least $1-\delta/2$ it holds uniformly over all $f \in \mathcal{{F}}$: $$\label{eq:Main_inequality01}
    L(f) - L_{n}(f) \leq  4\paren{R+F} \paren[3]{\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}})+ 4\mathcal{M}\sqrt{\frac{\ell \log(enD)}{n}}
          + (R+2F) \sqrt{\frac{\log{ \paren{\frac{2}{\delta}}}}{2n}}}
$$ where we recall that $\abs{f(\bx)} \leq F$ uniformly over all $\bx$ and $\abs{y} \leq R$.

In the next section we specify the constraints induced by the set $B$, and give explicit bounds for both Rademacher complexity and generalization error for $\ell_{2}$ and $\ell_{1}$ norm constraints.

Different penalty constraints and corresponding bounds
------------------------------------------------------

In what follows we denote $\Sigma 