Nota: Las siguientes no es una respuesta, pero sólo algunos pensamientos que
podría o no podría ser de ayuda para usted.
La primera nota que usted confundido(?) su desigualdad de signos. Creo que
quiero
$$
\gamma_{n}\left(\left\{ x\in\mathbb{R}^{n}\,\mid\,\left\Vert x\right\Vert ^{2}\geq\frac{n}{1-\varepsilon}\right\} \right){\color{rojo}\leq}e^{-\varepsilon n/4}
$$
y
$$
\gamma_{n}\left(\left\{ x\in\mathbb{R}^{n}\,\mid\,\left\Vert x\right\Vert ^{2}\geq\frac{{\rm de Seguimiento}\left(\Sigma\right)}{1-\varepsilon}\right\} \right){\color{rojo}\leq}e^{-\varepsilon n/4}.
$$
También tenga en cuenta que esta desigualdad sería mejor con los mayores valores
de $n$. Pero en general, esto no es cierto. Para ver esto, por ejemplo, el uso de
$$
\Sigma=\left(\begin{matrix}1\\
& 0\\
& & \ddots\\
& & & 0
\end{de la matriz}\right),
$$
o si usted quiere que su $\Sigma$ a ser positivo semidefinite, el uso de $\frac{1}{L\left(n-1\right)}$
en lugar de los ceros en la diagonal, donde $L$ es grande. Su estimación
sería entonces implica (desde $\left\Vert x\right\Vert ^{2}\geq\left|x_{1}\right|^{2}$)
que
$$
\mathbb{P}\left(\left|x_{1}\right|^{2}\geq\frac{1+\frac{1}{L}}{1-\varepsilon}\right)\leq\mathbb{P}\left(\left\Vert x\right\Vert ^{2}\geq\frac{1+\frac{1}{L}}{1-\varepsilon}\right)\leq e^{-\varepsilon n/4}\xrightarrow[n\to\infty]{}0,
$$
lo cual es absurdo.
Por lo tanto, el exponente de) el lado derecho de su estimación de alguna manera
debe involucrar a ${\rm trace}\left(\Sigma\right)$ en lugar de $n$
(Creo).
Lo que sigue es una adaptación de el argumento vinculado, pero me da
finalmente atascado al intentar optimizar el/encontrar a un buen valor de $\lambda$.
En primer lugar, desde $\Sigma$ es simétrica positiva semidefinite, hay
una matriz ortogonal $O\in\mathbb{R}^{n\times n}$$\Sigma=O \cdot {\rm diag}\left(\lambda_{1},\dots,\lambda_{n}\right)\cdot O^{T}$,
donde $\lambda_{1},\dots,\lambda_{n}\geq0$ son los valores propios de
$\Sigma$. Ahora podemos definir la raíz cuadrada $\sqrt{\Sigma}:=O\cdot {\rm diag}\left(\sqrt{\lambda_{1}},\dots,\sqrt{\lambda_{n}}\right) \cdot O^T\in\mathbb{R}^{n\times n}$
que satisface $\sqrt{\Sigma}^{T}=\sqrt{\Sigma}$$\sqrt{\Sigma}\sqrt{\Sigma}=\Sigma$.
Ahora, de las conocidas propiedades de la distribución normal, llegamos a la conclusión de
que $X:=\sqrt{\Sigma}g\sim N\left(0,\Sigma\right)$ donde $g\sim N\left(0,{\rm id}\right)$
es un estándar normal de la variable aleatoria distribuye.
También sabemos que la distribución normal estándar es invariante bajo
ortogonal de transformaciones, es decir,$h:=O^{T}g\sim N\left(0,{\rm id}\right)$.
Finalmente,
$$
\left\Vert X\right\Vert ^{2}=\left\Vert O{\rm diag}\left(\sqrt{\lambda_{1}},\dots,\sqrt{\lambda_{n}}\right)O^{T}g\right\Vert ^{2}=\left\Vert {\rm diag}\left(\sqrt{\lambda_{1}},\dots,\sqrt{\lambda_{n}}\right)h\right\Vert ^{2}=\sum_{i=1}^{n}\lambda_{i}h_{i}^{2},
$$
de modo que $\left\Vert X\right\Vert ^{2}$ (como se señaló a sí mismo) expectativa
$$
\mathbb{E}\left\Vert X\right\Vert ^{2}=\sum_{i=1}^{n}\lambda_{i}\mathbb{E}h_{i}^{2}=\sum_{i=1}^{n}\lambda_{i}={\rm de seguimiento}\left(\Sigma\right),
$$
desde $\mathbb{E}h_{i}^{2}={\rm Var}\left(h_{i}\right)=1$, desde
$h\sim N\left(0,{\rm id}\right)$.
Reordenando, podemos suponer $\lambda_{1}\geq\dots\geq\lambda_{j}>0=\lambda_{j+1}=\dots=\lambda_{n}$,
donde $j\in\left\{ 0,\dots,n\right\} $.
Ahora observe que el de Markov/Chebyscheff la desigualdad de los rendimientos, para arbitrario
$\lambda>0$,
\begin{eqnarray*}
\mathbb{P}\left(\left\Vert X\right\Vert ^{2}\geq{\rm trace}\left(\Sigma\right)+\delta\right) & = & \mathbb{P}\left(e^{\lambda\left\Vert X\right\Vert ^{2}}\geq e^{\lambda\left({\rm trace}\left(\Sigma\right)+\delta\right)}\right)\\
& \leq & e^{-\lambda\left({\rm trace}\left(\Sigma\right)+\delta\right)}\cdot\mathbb{E}\left(e^{\lambda\left\Vert X\right\Vert ^{2}}\right),
\end{eqnarray*}
donde
\begin{eqnarray*}
\mathbb{E}\left(e^{\lambda\left\Vert X\right\Vert ^{2}}\right) & = & \mathbb{E}\left(e^{\sum_{i=1}^{n}\lambda\lambda_{i}h_{i}^{2}}\right)\\
& = & \prod_{i=1}^{j}\mathbb{E}\left(e^{\lambda\lambda_{i}h_{i}^{2}}\right),
\end{eqnarray*}
por estocástica de la independencia de $\left(h_{1},\dots,h_{n}\right)$. El
el punto principal de la introducción de la $e^{\dots}$ plazo es este final
identidad, donde podemos sacar el producto de la expectativa por el
de la independencia.
Finalmente,
\begin{eqnarray*}
\mathbb{E}\left(e^{\gamma h_{i}^{2}}\right) & = & \frac{1}{\sqrt{2\pi}}\cdot\int_{\mathbb{R}}e^{\gamma x^{2}}\cdot e^{-x^{2}/2}\,{\rm d}x\\
& = & \frac{1}{\sqrt{2\pi}}\cdot\int_{\mathbb{R}}e^{-\left(\sqrt{\frac{1}{2}-\gamma}x\right)^{2}}\,{\rm d}x\\
& \overset{\omega=\sqrt{\frac{1}{2}-\gamma}x}{=} & \frac{1}{\sqrt{2\pi}\cdot\sqrt{\frac{1}{2}-\gamma}}\cdot\int_{\mathbb{R}}e^{-\omega^{2}}\,{\rm d}\omega\\
& = & \frac{1}{\sqrt{1-2\gamma}}
\end{eqnarray*}
para $\gamma<\frac{1}{2}$.
Con todo, llegamos a
$$
\mathbb{P}\left(\left\Vert X\right\Vert ^{2}\geq{\rm de seguimiento}\left(\Sigma\right)+\delta\right)\leq e^{-\lambda\left({\rm de seguimiento}\left(\Sigma\right)+\delta\right)}\cdot\prod_{i=1}^{j}\frac{1}{\sqrt{1-2\lambda\lambda_{i}}}.
$$
El problema es que ahora para optimizar este w.r.t. $0<\lambda<\frac{1}{2\lambda_{1}}$.
Una forma de simplificar(?) este es el uso de
$$
e^{-\lambda\left({\rm trace}\left(\Sigma\right)+\delta\right)}\cdot\prod_{i=1}^{j}\frac{1}{\sqrt{1-2\lambda\lambda_{i}}}=e^{-\left[\lambda\left({\rm trace}\left(\Sigma\right)+\delta\right)-\frac{1}{2}\sum_{i=1}^{j}\ln\left(1-2\lambda\lambda_{i}\right)\right]},
$$
donde uno sólo tiene que optimizar el exponente. Aún así, yo no lo vea
una manera fácil de determinar el valor óptimo de $\lambda$, ni una realidad
elección conveniente de $\lambda$.
Una elección inspirada por su vinculados notas de la conferencia es el uso de $\lambda=\frac{\delta/2}{{\rm trace}\left(\Sigma\right)+\delta}$
(porque en el estándar de gauss caso, tenemos $n={\rm trace}\left(\Sigma\right)$,
que es exactamente la elección más frecuente en las notas de la conferencia). Este sería
rendimiento
\begin{eqnarray*}
\mathbb{P}\left(\left\Vert X\right\Vert ^{2}\geq{\rm trace}\left(\Sigma\right)+\delta\right) & \leq & e^{-\delta/2}\cdot\prod_{i=1}^{j}\sqrt{\frac{{\rm trace}\left(\Sigma\right)+\delta}{{\rm trace}\left(\Sigma\right)+\delta-\delta\lambda_{i}}},
\end{eqnarray*}
que todavía no parece realmente buena.
Voy a intentar encontrar una buena selección de $\lambda$ aquí. Si se me ocurre algo, voy a editar el post.
