Exercise 14.4: Uniform Laws for Kernel Classes
(a)
Since \((\phi_j)_j\) is an orthonormal basis (Mercer), and \(f \in B_2(\delta) \subset L^2 (\P)\), there exists \(\theta \in \ell^2\)$ s.t. \(f = \sum_{j=1}^\infty \theta_j \phi_j\). Hence \begin{align} f(x_i) &= \bigl\langle \sum_j \theta_j \phi_j , \sum_{j’} \mu_{j’} \phi_{j’}(x_i) \phi_{j’} \bigr\rangle_\Hc \newline &= \sum_j \frac{\mu_j \theta_j \phi_j (x_i)}{\mu_j} = \sum_j \theta_j \phi_j (x_i) \, , \end{align} by Corollary 12.26. Hence \(\sum_{i=1}^n \varepsilon_i f(x_i) = \sum_{j=1}^\infty \theta_j z_j\). Assuming \(\mathbb{K}\) should have been \(\mathcal{D}\), and \(\delta\) was supposed to be \(\delta^2\) in the definition of \(\mathcal{D}\) (typos in the book), the result follows by Corollary 12.26 (\(\| f \|_\Hc^2 = \sum_j \frac{\theta_j^2}{\mu_j}\)) and Parseval (\(\| f \|_2^2 = \sum_j \theta_j^2\)).
(b)
For \(\theta \in \mathcal{D}\) \begin{align} \sum_j \frac{\theta_j^2}{\eta_j} \leq \sum_j \frac{\theta_j^2}{\mu_j} + \frac{\theta_j^2}{\delta^2} \leq 2 \, . \end{align}
(c)
\begin{align} \E \biggl[ \sup_{\mathcal{D}} \bigl| \sum_j \theta_j z_j \bigr| \biggr] &\overset{\text{(i)}}{\leq} \E \biggl[ \sup_\Ec \| \theta \|_2 \| z \|_2 \biggr] \newline &\overset{\text{(ii)}}{\leq} \biggl(2 \sum_j \eta_j\biggr)^{1/2} \E \biggl[ \biggl( \sum_{a, b, j} \varepsilon_a \varepsilon_b \phi_j(x_a) \phi_j(x_b) \biggr)^{1/2} \biggr] \newline &\overset{\text{(iii)}}{\leq} \biggl(2 \sum_j \eta_j\biggr)^{1/2} \biggl(\E \biggl[ \sum_{ij} \phi_j(x_i)^2 \biggr]\biggr)^{1/2} \newline &\overset{\text{(iv)}}{\leq} \biggl(2n \sum_j \mu_j \wedge \delta^2\biggr)^{1/2} \, , \end{align} where (i) follows by Cauchy-Schwarz, (ii) by \(\frac{\theta_j^2}{\eta_j} \leq 2\), (iii) by Jensen, and (iv) by \(\| \phi_j \|_2 = 1\).