Exercise 14.2: Properties of Local Rademacher Complexity
(a)
By argument analogous to Lemma 13.6, \(\delta \mapsto \frac{\bar{\Rc}_n(\delta)}{\delta}\) is non-increasing. Hence \begin{align} \frac{\bar{\Rc}_n(s)}{s} \leq \frac{\bar{\Rc}_n(\delta_n)}{\delta_n} \leq \delta_n \, , \end{align} for \(s \geq \delta_n\). On the other hand, when \(s < \delta_n\), \(\bar{\Rc}_n(s) \leq \bar{\Rc}_n(\delta_n) \leq \delta_n^2\) by definition.
(b)
Since \(C \geq 1\), \begin{align} \bar{\Rc}_n(t) \leq \bar{\Rc}_n(\sqrt{C} t) \leq \delta_n^2 \vee (\sqrt{C}t \delta_n) \, , \end{align} by (a). The r.h.s. is equal to \(\delta_n^2\) for \(t \geq \frac{\delta_n}{\sqrt{C}}\), which implies the minimal solution is at most \(\frac{\delta_n}{\sqrt{C}}\).