\leq \frac{2^{\frac{3}{2}}\ell^{\frac{1}{2}}W\sqrt{\sum_{i}\norm{\bx_{i}}^{2}_{\infty}}}{{n}}\paren{1+4\sqrt{\log{d}}},
    \end{aligned}$$ where in the last inequality we just used Jensen’s inequality in the similar fashion as for $\ell_{2}-$norm constaints. The Lemma is therefore proved.

In the similar way, as we used above, plugging in the result of Lemma \[lem:rad\_lasso\_con\] into \[lem: help\_lem01\] we get the following result.

\[prop:Lasso\_rad\_gen\] Let the function class $\mathcal{F}$ be as given by Equation  with $B=\{\norm{f}_{1} \leq W\}$. Then the following upper bounds for the empirical and true Rademacher complexity of the class $\mathcal{F}$ hold: $$\begin{aligned}
    \hat{\mathfrak{R}}_{\mathbb{S}}\paren{\mathcal{F}} &\leq \frac{W\sqrt{\ell}}{\sqrt{n}} \paren{\sqrt{\frac{2}{n}\sum_{j}\norm{\bx_{j}}_{\infty}^{2}}\paren{1 + 4 \sqrt{\log{d}}} + 4\sqrt{\norm[1]{\hat{\Sigma}}_{op}}\sqrt{{\log{enD}}}}; \\    {\mathfrak{R}}_{n}\paren{\mathcal{F}} &\leq
    \frac{W\sqrt{\ell}}{\sqrt{n}} \paren{\sqrt{2\ee{}{\norm{\bx_{j}}_{\infty}^{2}}}\paren{1 + 4 \sqrt{\log{d}}} + 4\sqrt{ \ee[1]{}{\norm[1]{\hat{\Sigma}}_{op}}}\sqrt{{\log{enD}}}}.
    \end{aligned}$$ Furthermore, in the similar vein to the $\ell_{2}$ regularization case, bounds on the generalization error is obtained by simply applying Theorem \[thm:main\_theorem01\] and plugging-in the upper bounds on the empirical Rademacher complexity. with probability at least $1-\delta/2$ we have for all $f \in \mathcal{{F}}$: $$\begin{aligned}
    L(f) \leq L_{n}(f) & + C_{1} \paren{ \frac{W\sqrt{\ell}}{\sqrt{n}} \paren{\sqrt{\frac{2}{n}\sum_{j=1}^{n}\norm{\bx_{j}}_{\infty}^{2}}\paren{1 + 4 \sqrt{\log{d}}} + 4\sqrt{\norm[1]{\hat{\Sigma}}_{op}}\sqrt{{\log{enD}}}} + WK\sqrt{\frac{\log(\frac{2}{\delta})}{2n}}} \\ 
    & + C\sqrt{\frac{\log(\frac{2}{\delta})}{2n}}.
    \end{aligned}$$ Or an alternative (distribution dependent bound) in the form: $$\begin{aligned}
L(f) \leq L_{n}(f) & + C_{1}\paren{ \frac{W\sqrt{\ell}}{\sqrt{n}} \paren{2^{\frac{1}{2}}\sqrt{\ee{}{\norm{\bx}_{\infty}^{2}}}\paren{1 + 4 \sqrt{\log{d}}} + 4\sqrt{\ee{}{\norm[1]{\hat{\Sigma}}_{op}}}\sqrt{{\log{enD}}}}} + C\sqrt{\frac{\log(\frac{2}{\delta})}{2n}},     
    \end{aligned}$$ where $C_{1} =4(R+WK)$, $C = 