*generalization error* of the class $\mathcal{F}$, as $Z := \sup\limits_{f \in \mathcal{F}} \big(L(f) - \hat{L}_{n}(f) \big)$. The main result of this section is a high probability upper bound on the deviations of $Z$ under the different assumptions on the regularization constraints in $B$.

The expectation and deviation of the generalization error is the typical measure to control the statistical performance of the underlying model class and it was widely studied in [@bartlett2002rademacher],[@koltchinskii2001rademacher]. In these works the framework of Rademacher complexity is used as the complexity measure for structured regularized risk estimation methods, including kernel methods.

Let now $\bm{\sigma}:=(\sigma_{i})_{i=1}^{n}$ be a $n$-vector of i.i.d. random variables independent of $\mathbb{S}$, uniformly distributed over $\{-1,+1\}$ (Rademacher random variables). For a given loss function $l$, such that $|l(\cdot,\cdot)| \leq C$ and for all $f$ in (an arbitrary) model class $\mathcal{G}$, with probability at least $1-\delta$ it holds (see for example [@bartlett2002rademacher]):

$$L(f) \leq L_{n}(f)+2\mathfrak{R}_{n}(l \circ \mathcal{\mathcal{G}}) + C\sqrt{\frac{\log \delta^{-1}}{2n}},
\label{eq:gen_error}$$

where $$\begin{aligned}
\mathfrak{R}_{n}(l \circ \mathcal{F}) := E \left[\sup\limits_{f \in \mathcal{F}} \frac{1}{n} \sum\limits_{i=1}^{n}\sigma_{i}l(f(\bx_{i}),y_{i})) \right],\end{aligned}$$ is the *Rademacher complexity* of the model class $\mathcal{F}$, the last expectation being taken under the product distribution of $(\mbs,\bm{\sigma})$, where $l \circ \mathcal{G}:= \{ (\bx,y) \mapsto l(f(\bx),y)  | f \in 