Exercise 3.16: Different Forms of Functional Bernstein Inequality
(a)
Let \(t = \frac{n \delta^2}{c_1 \gamma^2 + c_2 b \delta}\). Using the quadratic formula, we can solve for \(\delta\) \begin{align} \delta &= \frac{ c_2 b t + \sqrt{c_2^2 b^2 t^2 + 4 c_1 n \gamma^2 t} }{ 2n } \newline &\leq \frac{ 2 c_2 b t + 2 \gamma \sqrt{c_1 n t} }{ 2 n } = \frac{c_2 b t}{n} + \gamma \sqrt{\frac{c_1 t}{n}} \, , \end{align} where we used \(\sqrt{a^2 + b^2} \leq a + b\) for \(a, b \geq 0\).
(b)
We will w.l.o.g. assume that \(\mathscr{F}\) is symmetrised, i.e., for every \(f \in \mathscr{F}\), \(-f \in \mathscr{F}\). This ensures that the random variable \begin{align} Z = \sup_{f \in \mathscr{F}} \frac{1}{n} \sum_{i=1}^n f(X_i) \, , \end{align} is almost surely non-negative, and thus \(\E[Z] \geq 0\).
Substituting the bound for \(\gamma^2 \leq \sigma^2 + c_3 b \E [Z]\) and using the \(\sqrt{a^2 + b^2} \leq a + b\) for \(a, b \geq 0\) inequality \begin{align} \gamma \sqrt{\frac{c_1 t}{n}} \leq \sigma \sqrt{\frac{c_1 t}{n}} + \sqrt{\frac{c_1 c_3 b t \E [Z]}{n}} \, , \end{align} where we are using \(\E[Z] \geq 0\) from above. Since for any \(\epsilon > 0\) \begin{align} \left( \sqrt{\frac{c_1 c_3 b t}{2 \epsilon n}} - \sqrt{\epsilon \E[Z]} \right)^2 = \frac{c_1 c_3 bt}{2 \epsilon n} + \epsilon \E [Z] - \sqrt{2 \frac{c_1 c_3 b t \E [Z]}{n}} \geq 0 \, , \end{align} we can upper bound \begin{align} \sqrt{\frac{c_1 c_3 b t \E [Z]}{n}} \leq \frac{c_1 c_3 b t}{2 \sqrt{2} \varepsilon n} + \frac{\epsilon \E[Z]}{\sqrt{2}} \, . \end{align} The required result can be obtained by upper bounding the right hand side by its \(\sqrt{2}\) multiple, and substituting the implied bound \begin{align} \gamma \sqrt{\frac{c_1 t}{n}} \leq \sigma \sqrt{\frac{c_1 t}{n}} + \frac{c_1 c_3 b t}{2 \varepsilon n} + \epsilon \E[Z] \, , \end{align} into our result from (a).