Exercise 4.7: Basic Properties of Rademacher Complexity
(a)
For \(\Rc_n(\F) \le \Rc_n(\operatorname{conv} \F)\), use that \(\F \sub \operatorname{conv} \F\). For the converse inequality, use that every \(\overline{f} \in \operatorname{conv} \F\) can be written as \begin{equation} \overline{f} = \sum_{j=1}^m \alpha_j f_j \end{equation} for \((\alpha_j)_{j=1}^m \sub [0, 1]\), \(\sum_{j=1}^m \alpha_j = 1\), and \((f_j)_{j=1}^m \sub \F\). Then \begin{equation} \abs{\sum_{i=1}^n \e_i \overline{f}(X_i)} \le \sum_{j=1}^m \alpha_i\abs{ \sum_{i=1}^n \e_i f_j(X_i) } \le \sup_{f \in \F}\, \abs{ \sum_{i=1}^n \e_i f(X_i) }, \end{equation} so divide by \(n\) and take expectations to conclude.
(b)
This is just the triangle inequality. Consider \(\F = \set{f}\) to find equality.
(c)
Use the triangle inequality and uniform boundedness of \(g\): \begin{equation} \sup_{f \in \F}\, \abs{ \frac1n \sum_{i=1}^n \e_i f(X_i) + \frac1n \sum_{i=1}^n \e_i g(X_i) } \le \sup_{f \in \F}\, \abs{ \frac1n \sum_{i=1}^n \e_i f(X_i) } + \abs{ \sum_{i=1}^n \e_i } \frac{\norm{g}_\infty}{n}. \end{equation} Then conclude by taking the expectation and using that \(\E[\abs{\sum_{i=1}^n \e_i}]\le \sqrt{n}\), which follows from Cauchy–Schwarz.