} + \paren{R+F}\sqrt{\frac{\log\paren{\frac{2}{\delta}}}{2n}}}
    \end{aligned}$$

Furthermore, 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[3]{W\sqrt{\frac{\ell}{n}} \paren{\sqrt{2\tr{\hat{\Sigma}}} + 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}$$

Alternatively, using the bound on the true Rademacher complexity we obtain with probability at least $1-\delta$: $$\begin{aligned}
    L(f) \leq L_{n}(f) & + C_{1}W \sqrt{\frac{\ell}{n}} \paren{ \sqrt{2\tr{\Sigma}} + 4
        \sqrt{\ee[1]{}{\norm[1]{\hat{\Sigma}}_{op}}}\sqrt{\log{enD}}}
    +C\sqrt{\frac{\log({\frac{1}{\delta}})}{2n}},
    \end{aligned}$$ where $C_{1} = 4 \paren{R+WK}$, $C:=\paren{R+WK}^{2}$.

\[rem:gen\_error\] Consider the simple case $\Sigma = \mathbbm{I}_{d}$. Then, in the last bound, the first term scales as $\tr{\Sigma} = d$, but the second term scales like $\e[1]{\norm[1]{\hat{\Sigma}}_{op}}$, which is, due to classical matrix concentration results [@Tropp:15], up to a $\log(d)$ factor the same as $\norm{\Sigma}_{op} = 1$. This implies: $$\begin{aligned}
    L(f) \leq L_{n}(f) & + C_{1} W \sqrt{\frac{\ell}{n}} \paren{ {\sqrt{2d} + 8C_{3}
    \sqrt{\log{d}}\sqrt{\log{enD}}}} +C\sqrt{\frac{\log({\frac{1}{\delta}})}{2n}},\end{aligned}$$ where $C_{3}$ is some universal numerical constant and $C=(R+WK)^{2}$, $C_{1}=4(R+WK)$. In this case, the first term contributes to the bound exponentially more ($d$ against $\log d$) comparing to the second. Furthermore, if the eigenvalues of $\Sigma$ decay geometrically fast, i.e. $\lambda_{k} \leq \lambda\rho^{k-1}$, with $0 < \rho <1$ for $k \in [d]$, we have $\tr{\Sigma} \leq \frac{\lambda}{1-\rho}$ and $\norm{\Sigma}_{op} = \lambda$ and 