Exercise 14.1: Bounding the Lipschitz Constant

chapter 14 symmetrisation

Let $\F$ be a star-shaped and $1$-uniformly-bounded function class. First, manipulate the supremum to a difference between a squared $n$-norm and squared population norm: \begin{equation} \E[\,\sup_{\norm{f}_2 \le t} \norm{f}_n]^2 \le \E[\,\sup_{\norm{f}_2 \le t} (\norm{f}_n^2 - \norm{f}_2^2)] + t^2. \end{equation} Then, by symmetrisation and $1$-uniform-boundedness plus the Ledoux–Talagrand contraction inequality for the Rademacher complexity, \begin{align} \E[\,\sup_{\norm{f}_2 \le t} (\norm{f}_n^2 - \norm{f}_2^2)] &\le 2 \E\sbrac{\,\sup_{\norm{f}_2 \le t}\,\abs{\frac1n \sum_{i=1}^n \e_i f^2(x_i)}} \newline &\le 4 \E\sbrac{\,\sup_{\norm{f}_2 \le t}\,\abs{\frac1n \sum_{i=1}^n \e_i f(x_i)}} \newline &\le 4 \delta_n^2 \newline &\le 4 t^2. \end{align} This is exactly like the first chain inequalities in the proof of Lemma 14.9. We conclude that \begin{equation} \E[\,\sup_{\norm{f}_2 \le t} \norm{f}_n]^2 \le 5 t^2. \end{equation}