of its empirical version $\hat{\mathfrak{R}}_{\mathbb{S}}(\mathcal{F})$, since we observe that changing one point in $\mathbb{S}$ changes $\hat{\mathfrak{R}}_{\mathbb{S}}(\mathcal{F})$ by at most $\frac{F}{n}$, so that by McDiarmid’s inequality, with probability at least $1-\delta/2$ it holds: $$\begin{aligned}
        \mathfrak{R}_{n}\paren{\mathcal{F}} \leq \hat{\mathfrak{R}_{\mathbb{S}}}\paren{\mathcal{F}} + F\sqrt{\frac{\log{\frac{2}{\delta}}}{2n}}.\end{aligned}$$

This argument, together with the aforementioned reasoning, implies that in order to obtain high-probability upper bounds for the generalization error $Z$ of model class $\mathcal{F}$, it is sufficient to obtain bounds on its empirical Rademacher complexity based on the sample $\mathbb{S}$. More precisely, with probability at least $1-\delta/2$ it holds for all $f \in \mathcal{F}$ that: $$\begin{aligned}
\label{eq:risk_ineq}
    L(f) \leq L_{n}(f) + 2L\hat{\mathfrak{R}}_{\mathbb{S}}\paren{\mathcal{F}} + 2LF\sqrt{\frac{\log{\frac{2}{\delta}}}{2n}} + L_{R,F,B}\sqrt{\frac{\log{\frac{2}{\delta}}}{2n}}.\end{aligned}$$ In the next part we concentrate mainly on the bounds on the (empirical) Rademacher complexity of the model class $\mathcal{{F}}$ of PLRT, but also provide bounds on the true Rademacher complexity.

(Empirical) Rademacher complexity and generalization error deviation bound for the class of PLRT
------------------------------------------------------------------------------------------------

Recalling the formal definition of the predictor class in , we observe that for a fixed a element (tree) $T \in \mathcal{T}_{l}$, and some partition generated by the family $(i_{s},t_{s})_{s \in T^{\circ}} \in S$, we obtain a submodel class $\mathcal{{F}}_{T,\paren{i_{s},t_{s}}_{s \in T^{\circ}}}$ which is a product of the decision models 