Exercise 6.12: Sharpened Matrix Bernstein Inequality
(a)
We assume \(S_n\) is symmetrised so that \(\phi(\lambda S_n)\) is well-defined. Combining \(\phi \geq 0\) with Markov’s inequality \begin{align} \P (\gamma_\text{max}(S_n) \geq \delta) = \inf_{\lambda > 0} \P (\phi(\gamma_\text{max}(\lambda S_n)) \geq \phi(\lambda \delta)) \leq \inf_{\lambda > 0} \frac{\E[\phi(\gamma_\text{max}(\lambda S_n))]}{\phi(\lambda \delta)} \leq \inf_{\lambda > 0} \frac{\tr(\E [\phi(\lambda S_n)])}{\phi(\lambda \delta)} \, . \end{align}
(b)
The steps in this part largely mirror Exercise 2.7(a): Since \(\phi(\lambda) = e^{\lambda} - \lambda - 1 = \sum_{n=2}^\infty \frac{\lambda^n}{n!}\), we have \begin{align} \E [e^{\lambda Q_i}] &= I + \lambda \cdot 0 + \sum_{n=2}^\infty \frac{\lambda^n}{n!} \E [Q_i^n] \newline &\overset{\text{(i)}}{\preceq} I + \phi(\lambda) \V(Q_i) \newline &\overset{\text{(ii)}}{\preceq} e^{\phi(\lambda) \V (Q_i)} \, , \end{align} where (i) follows by the assumed \(\| Q_i \|_2 \leq 1\), and (ii) from Exercise 6.4. Conclude by appealing to the matrix monotonicity of the logarithm.
(c)
Since \(\E [S_n] = 0\) \begin{align} \tr (\E [\phi(\lambda S_n)]) &= \tr (\E[e^{\lambda S_n} - I]) \newline &\overset{\text{(i)}}{\leq} \tr \bigl(\exp \bigl\lbrace \sum_i \log \Psi_{Q_i} (\lambda) \bigr\rbrace - I \bigr) \newline &\leq \tr \bigl(\exp \bigl\lbrace \phi(\lambda) \sum_i \V(Q_i) \bigr\rbrace - I \bigr) \, . \end{align}
Defining \(f(\gamma) = e^\gamma - 1\), we see \(f\) is convex with \(f(0) = 0\), and thus \begin{align} f(\gamma_i) \leq \bigl(1 - \tfrac{\gamma_i}{\| \bar{V} \|_2} \bigr) f(0) + \tfrac{\gamma_i}{\| \bar{V} \|_2} f(\| \bar{V} \|_2) = \tfrac{\gamma_i}{\| \bar{V} \|_2} f(\| \bar{V} \|_2) \, . \end{align} Therefore \(\tr(e^{\phi(\lambda) \bar{V}} - I) \leq (e^{\phi(\lambda) \|\bar{V}\|_2} - 1) \tfrac{\tr(\bar{V})}{\| \bar{V} \|_2} \leq e^{\phi(\lambda) \|\bar{V}\|_2} \tfrac{\tr(\bar{V})}{\| \bar{V} \|_2}\) as desired.
notes
- The quantity \(\frac{\tr(\bar{V})}{\| \bar{V} \|_2}\) is sometimes referred to as the intrinsic dimension of \(\bar{V}\).