Bounded independent matrix Bernstein bound from the trace exponential

Fix $0<s<3\mathrm{/}R$. If $\mathrm{\mid }x\mathrm{\mid }\le R$ and $k\ge 2$ is an integer, then $x^k\le R^{k-2}{x}^2$, including odd $k$ and negative $x$. Applying the spectral calculus and taking expectations gives $\mathbb{E}{B}_i^k⪯R^{k-2}\mathbb{E}{B}_i^2$. Since $k!\ge 2\cdot 3^{k-2}$ for every $k\ge 2$ (start at $k=2$ and multiply by $k+1\ge 3$), the exponential series and $\mathbb{E}{B}_i=0$ yield $\mathbb{E}\exp (s{B}_i)⪯I+g(s)\mathbb{E}{B}_i^2⪯e^{g(s)v}I$, where $g(s)=s^2\mathrm{/}[2(1-sR\mathrm{/}3)]$. The first inequality is the sum of the convergent geometric majorant ${\sum }_{k\ge 2}{s}^k{R}^{k-2}\mathrm{/}k!\le g(s)$, and the second uses $0⪯\mathbb{E}{B}_i^2⪯vI$ and the scalar inequality $1+a\le e^a$. Termwise expectation is justified by the uniform norm majorant ${\sum }_k(sR{)}^k\mathrm{/}k!$.

Let $Y_j={\sum }_{i=1}^j{B}_i$, with $Y_0=0$. For each fixed value of $Y_{j-1}$, [F2] and integration over the independent $B_j$ give ${\mathbb{E}}_{B_j}\mathrm{tr}\exp (s{Y}_{j-1}+s{B}_j)\le \mathrm{tr}(\exp (s{Y}_{j-1})\mathbb{E}\exp (s{B}_j))\le e^{g(s)v}\mathrm{tr}\exp (s{Y}_{j-1})$. The last implication follows because $P⪰0$ and $Q⪯cI$ imply $\mathrm{tr}(PQ)\le c\mathrm{tr}P$: diagonalize $P$ and sum its nonnegative eigenvalues times the bounded diagonal quadratic forms of $Q$. Successive integration using [F3] and iteration from $\mathrm{tr}I=q$ prove $\mathbb{E}\mathrm{tr}\exp (sY)\le q{e}^{mg(s)v}$.

By [F1], $\mathrm{tr}\exp (sY)\ge \exp (s{\lambda }_{\max }(Y))$. Markov's inequality [F4] and step 2.1 therefore give $\mathbb{P}\{{\lambda }_{\max }(Y)\ge u\}\le q\exp (-su+mg(s)v)$ for every $u>0$ and $0<s<3\mathrm{/}R$. If $v>0$, choose $s=u\mathrm{/}(mv+Ru\mathrm{/}3)$, which belongs to that interval. Substitution gives $-su+mg(s)v=-u^2\mathrm{/}[2(mv+Ru\mathrm{/}3)]$, proving the stated tail bound. The same fixed-parameter bound with $>$ in place of $\ge$ will also be used below.

For $b>0$ set $u=\sqrt{2mvb}+2Rb\mathrm{/}3$. Expanding its square shows $u^2\ge 2b(mv+Ru\mathrm{/}3)$: with $a=\sqrt{2mvb}$ and $c=2Rb\mathrm{/}3$, the two sides are respectively $a^2+2ac+c^2$ and $a^2+ac+c^2$. Thus step 3.1 bounds the one-sided failure by $q{e}^{-b}$. Applying the same argument to $-B_i$ and taking the union of the two failures bounds the norm failure by $2q{e}^{-b}$, since the norm of a Hermitian matrix is the larger of its maximum eigenvalue and the maximum eigenvalue of its negative.

Finally, if $v=0$, then for each coordinate vector $e_j$, $\mathbb{E}\mathrm{\parallel }{B}_i{e}_j{\mathrm{\parallel }}_2^2=e_j^{\ast }(\mathbb{E}{B}_i^2)e_j=0$. A nonnegative random variable with zero expectation vanishes almost surely: otherwise one of the events where it exceeds $1\mathrm{/}n$ would have positive probability and positive contribution to the expectation. Intersecting the finitely many full-probability coordinate events gives $B_i=0$ almost surely; a further finite intersection covers all $i$. The trace mgf is then $q$ and both strict positive-threshold events are empty. This covers the remaining case and completes all conclusions.