Exercise 4.5: Necessity of Vanishing Rademacher Complexity

bounded differences inequality chapter 4

(a)

Observe that \begin{equation} \norm{\mathbb{S}_n}_{\overline{\F}} = \sup_{f \in \F}\, \abs{ \frac1n \sum_{i=1}^n \e_i f(X_i) - \frac1n \sum_{i=1}^n \e_i \E[f] } \ge \sup_{f \in \F}\, \abs{ \frac1n \sum_{i=1}^n \e_i f(X_i) } - \abs{ \sum_{i=1}^n \e_i } \frac{\sup_{f \in \F}\,\abs{ \E[f] }}{n} \end{equation} and, by Cauchy–Schwarz, \begin{equation} \E\sbrac{ \abs{ \sum_{i=1}^n \e_i } } \le \sqrt{ \E\sbrac{ \parens{ \sum_{i=1}^n \e_i }^2 } } = \sqrt{ \E\sbrac{ \sum_{i=1}^n \e_i^2 } } = \sqrt{n}. \end{equation}

(b)

By (a) and (4.21), \begin{equation} \frac12\parens{ \mathcal{R}(\F) - \frac{\sup_{f \in \F}\,\abs{ \E[f] }}{\sqrt{n}} } \le \frac12 \E_{X, \e}[\norm{\mathbb{S}_n}_{\overline \F}] \le \E_X[\norm{\P_n - \P}_\F], \end{equation} and use the Bounded differences inequality as in the proof of Theorem 4.10.