{\mathcal{G}} \}$ is the loss function class associated to $\cG$. If we treat the sample $\mathbb{S}$ as fixed, we introduce the *empirical Rademacher complexity*

$$\hat{\mathfrak{R}}_{\mbs}(l \circ \mathcal{F}) := E_{\bm{\sigma}}\left[ \sup\limits_{f \in \mathcal{F}} \frac{1}{n}\sum\limits_{i=1}^{n}\sigma_{i}l(f(\bx_{i}),y_{i}))\right],
\label{eq:empirical_rademacher_f}$$

so that $\mathfrak{R}_{n}(l \circ \mathcal{F}) = E_{\mathbb{S} \sim P^{\otimes n}_{x,y}}\left[\hat{\mathfrak{R}}_{\mbs}(l \circ \mathcal{F})\right] $. It is also known (see for example [@bartlett2005local]) that if the loss-function $\ell$ is $L$-Lipschitz in its second argument,i.e. $\forall y \in \mathbf{Y}$ $ |l(a,y)-l(b,y)| \leq L|a-b| \; \forall a,b \in \mathbb{R}$ then: $$\hat{\mathfrak{R}}_{\mbs}(l \circ \mathcal{F}) \leq L \hat{\mathfrak{R}}_{\mbs}(\mathcal{{F}}),
\label{eq:ledoux}$$ and for we get for all $f$ in the class $\mathcal{F}$: $$\label{eq:gen_bound}
L(f) \leq L_{n}(f)+2L \mathfrak{R}_{n} ( \mathcal{F}) + C\sqrt{\frac{\log\delta ^{-1}}{2n}}.$$ Now, for the PRLT learning algorithm we consider the squared loss function $l(y',y)=(y-y')^2$. Recall that from the previous assumptions we have $\norm{\bx}_{2} \leq K$ and $|y| \leq R$ almost surely with respect to ${P}_{X,Y}$.

Assume also that for all $\bx$ with $\norm{\bx}_{2}\leq K$ and $f\in \cF$ it holds that $\abs{f(\bx)} \leq F$ (for linear predictors, the constant $F$ depends on the norm-constraints in the set $B$ and will be specified later). Then, we have easily for the squared-loss function: $$\begin{aligned}
|l(\cdot,\cdot)| \leq (R+F)^2 := L_{R,F,B}.\end{aligned}$$ Furthermore, we can control $\mathfrak{R}_{n}(\mathcal{F})$ by means 