From the note on union bound I found the following
Now I have the following lemma on multivariate normal distribution (with dimension $d$): Let $x \sim \mathcal{N}(0, \nu(\delta/M)\Sigma^{-1})$ where $\nu$ is a scalar function. For any $\delta > 0$,
\begin{equation}
\mathbb{P}\left(\|x\|_{\Sigma} \leq c \sqrt{d\nu(\delta/M)\log(dM/\delta)}\right) > 1-\delta/M
\end{equation}
where $c$ is a constant.
My question is if I sample $x_1, \cdots, x_M$ from the normal distribution and want to give union bound over all sampled $x_i$'s, can I just say the following?
\begin{equation}
\mathbb{P}\left(\max_{i \in \{1,2, \cdots, M\}}\|x_i\|_{\Sigma} \leq c \sqrt{d\nu(\delta/M)\log(dM/\delta)}\right) > 1-\delta
\end{equation}
My confusion is whether the term $c \sqrt{d\nu(\delta/M)\log(dM/\delta)}$ in the last probability term should also change because of doing union bound over $M$ things. But based on Fact 1.3 it seems it shouldn't?
Best Answer
$$\begin{aligned}\mathbb{P}\left(\max_{i \in \{1,2, \cdots, M\}}\|x_i\|_{\Sigma} \leq c \sqrt{d\nu(\delta/M)\log(dM/\delta)}\right) &= \mathbb{P}\left(\bigcap_{i \in \{1,2, \cdots, M\}}\|x_i\|_{\Sigma} \leq c \sqrt{d\nu(\delta/M)\log(dM/\delta)}\right)\\ &= 1-\mathbb{P}\left(\bigcup_{i \in \{1,2, \cdots, M\}}\|x_i\|_{\Sigma} > c \sqrt{d\nu(\delta/M)\log(dM/\delta)}\right) \end{aligned}$$
From the union bound, $\mathbb{P}\left(\bigcup_{i \in \{1,2, \cdots, M\}}\|x_i\|_{\Sigma} > c \sqrt{d\nu(\delta/M)\log(dM/\delta)}\right)< M\cdot \frac{\delta}M=\delta$ hence $$\mathbb{P}\left(\max_{i \in \{1,2, \cdots, M\}}\|x_i\|_{\Sigma} \leq c \sqrt{d\nu(\delta/M)\log(dM/\delta)}\right) > 1-\delta$$