Exercise 4.5: Necessity of Vanishing Rademacher Complexity

bounded differences inequality chapter 4

(a)

Observe that $$\begin{array}{}\text{(1)}& \Vert {\mathbb{S}}_n{\Vert }_{\bar{\mathcal{F}}}=\underset{f\in \mathcal{F}}{sup}|\frac{1}{n}\sum _{i=1}^n{\epsilon }_{i}f(X_i)-\frac{1}{n}\sum _{i=1}^n{\epsilon }_i\mathbb{E}[f]|\ge \underset{f\in \mathcal{F}}{sup}|\frac{1}{n}\sum _{i=1}^n{\epsilon }_{i}f(X_i)|-\left|\sum _{i=1}^n{\epsilon }_i\right|\frac{\underset{f\in \mathcal{F}}{sup}|\mathbb{E}[f]|}{n}\end{array}$$ and, by Cauchy–Schwarz, $$\begin{array}{}\text{(2)}& \mathbb{E}\left[\left|\sum _{i=1}^n{\epsilon }_i\right|\right]\le \sqrt{\mathbb{E}\left[{\left(\sum _{i=1}^n{\epsilon }_i\right)}^2\right]}=\sqrt{\mathbb{E}\left[\sum _{i=1}^n{\epsilon }_i^2\right]}=\sqrt{n}.\end{array}$$

(b)

By (a) and (4.21), $$\begin{array}{}\text{(3)}& \frac{1}{2}(\mathcal{R}(\mathcal{F})-\frac{\underset{f\in \mathcal{F}}{sup}|\mathbb{E}[f]|}{\sqrt{n}})\le \frac{1}{2}{\mathbb{E}}_{X,\epsilon }[\Vert {\mathbb{S}}_n{\Vert }_{\bar{\mathcal{F}}}]\le {\mathbb{E}}_X[\Vert {\mathbb{P}}_n-\mathbb{P}{\Vert }_{\mathcal{F}}],\end{array}$$ and use the Bounded differences inequality as in the proof of Theorem 4.10.