I am reading the proof of Lemma 18 in Appendix A in [1]:
To prove this lemma the author starts with the vector Bernstein inequality Theorem 12 in [2]:
Theorem 12 is established for $y = \sum_{i=1}^n x_i$ where $x_i$ is a vector-values random variable. Then, for $z = \frac{1}{n}\sum_{i=1}^n x_i$, in the end of the proof of Lemma 18 in [1], the author justifies that the Bernstein inequality in Theorem 12 in [2] can be written as
$$P(\|z \| \geq \epsilon ) \leq \exp \left\{-n\frac{\epsilon^2}{8\sigma^2}+ \frac{1}{4}\right\}\tag{1}$$ by utilizing $V \leq \frac{1}{n}\sigma^2$. I do not understand the connection here. Could you please someone provide more details on how $(1)$ is derived?
[1] Jonas Moritz Kohler, Sub-sampled Cubic Regularization for Non-convex optimization, 2017
[2] David Gross, Recovering Low-Rank Matrices From Few Coefficients In Any Basis, 2010
We assume that $m=n$. Using the correct bound $V \le n\sigma^2$, separate two cases.
$(1)$ If $n\epsilon \le \sqrt{V}$ then $\frac{n\epsilon^2}{8\sigma^2}\le \frac{n^2\epsilon^2}{8V}\le \frac18$, so $(1)$ is vacuously true.
$(2)$ If $n\epsilon = \sqrt{V}+t$ with $t >0$, then $$\frac{ n\epsilon^2} {8\sigma^2}-\frac14 \le \frac{n^2\epsilon^2}{8V}-\frac14 =\frac{(V+2t\sqrt{V}+t^2)-2V}{8V} \le \frac{2t^2}{8V}=\frac{t^2}{4V} \,,$$ using $(\sqrt{V}-t)^2 \ge 0$ in the second inequality. Thus by Theorem 12, $$ P(\|z\| \ge \epsilon)=P(N \le n\epsilon) \le \exp\Bigl(-\frac{t^2}{4V} \Bigr) \le \exp\Bigl( -\frac{ n\epsilon^2} {8\sigma^2}+\frac14 \Bigr) \,. $$