Deriving Sample Complexity from given expectation bound In equations (1.6) and (1.7) of this paper, the authors provide an upper bound on an expectation term and the corresponding sample complexity. I am a bit confused as to how they derive their sample complexity term (1.7), though I could be missing something obvious here.
The bound is of the form:
\begin{align*}
\sqrt{E \| Y_n -Y\|^2} \le C \left [ \sqrt{\Gamma \frac{A\log p}{n}} + \Gamma \frac{B\log p \log(np)}{n}\right] \|\Sigma \|
\end{align*}
They state that if you assume $n \le p$, and select a tolerance $\epsilon \in (0,1)$, then there is a (different) constant C such that
\begin{align*}
n \ge C \left[ \frac{A \log p}{\epsilon^2} + \frac{B \log^2 p}{\epsilon} \right]\Gamma \implies \| Y_n - Y\| \le \epsilon\| \Sigma \|.
\end{align*}
My working so for is:
\begin{align*}
P(\| Y_n - Y\| > \epsilon \|\Sigma\|)
& \le \frac{1}{\epsilon\|\Sigma\|} E \| Y_n -Y\|\\
&\le \frac{1}{\epsilon\|\Sigma\|} \sqrt{E \| Y_n -Y\|^2}\\
&\le \frac{1}{\epsilon}C \left [ \sqrt{\Gamma \frac{A\log p}{n}} + \Gamma \frac{B\log p \log(np)}{n}\right]\\
&\le \frac{1}{\epsilon}C \left [ \sqrt{\Gamma \frac{A\log p}{n}} + \Gamma \frac{B\log^2 p }{n}\right]
\end{align*}
where the first inequality holds by Markov's inequality, the second by Jensen's, the third by the given bound, and the fourth by the assumption that $n\le p$. I'm just not sure how they get their sample complexity from here.
 A: I think you did the main part of the job. One useful observation to keep in its toolkit is that for $a,b\ge 0$,
$$
\max(a,b)\le a+b\le 2\max(a,b)
$$
so that since we do not care about the value of the universal constant $C$, we may as well treat both terms separately, depending on which one dominates. Imagine for example that
$$
\sqrt{\Gamma \frac{A\log p}{n}}\ge \Gamma \frac{B\log^2 p}{n}.\tag{1}
$$
Then for $\|Y_n-Y\|\le \varepsilon \|\Sigma\|$ to hold with probability at least $0.99$, it suffices that
$$
\frac{2C}{\varepsilon}\sqrt{\Gamma \frac{A\log p}{n}}\le 0.01.
$$
For sure, this holds if
$$
n\ge C'\frac{A\log p}{\varepsilon^2}\Gamma.
$$
Similarly, if the reverse inequality of (1) holds, then we get the same high probability result if we set
$$
n\ge C''\frac{B\log^2 p}{\varepsilon}\Gamma.
$$
So, in general, taking
$$
n\ge \max(C,C'')\left(\frac{A\log p}{\varepsilon^2}+\frac{B\log^2 p}{\varepsilon}\right)\Gamma
$$
will always give $\|Y_n-Y\|\le \varepsilon \|\Sigma\|$, regardless of the regime we are in.
