Exercise 14.8: Estimation of Nonparametric Additive Models
Let \(\G\) be a univariate base class which is convex, contains the zero function, and is \(1\)-uniformly bounded. Consider the class \(\F\) of multivariate functions of the form \begin{align} f \colon x \in \R^d \mapsto \sum_j g_j (x_j) \in \R \, , \end{align} where \(g_j \in \G\) for each \(j\). Consider a distribution over inputs \(x \in \R^d\) with two-way independent components, and assume that \(\E[g_j(x_j)] = 0\) for all \(j\). Finally, let \(\delta_n\) be the smallest positive solution to \(\bar{\Rc}_n(\delta ; \G) \leq \delta^2\), and let \(\varepsilon_n\) be the smallest positive solution of \(\bar{\Rc}_n(\varepsilon ; \F) \lesssim d \varepsilon_n^2\).
We show that \(\delta_n \lesssim \sqrt{d} \varepsilon_n\), which we show by demonstrating that \(\bar{\Rc}_n(\sqrt{d} \varepsilon_n ; \F) \lesssim d \varepsilon_n^2\) \begin{align} \bar{\Rc}_n (\sqrt{d} \varepsilon_n ; \F) &= \E \biggl[ \sup_{\|f\|_2 \leq \sqrt{d} \varepsilon_n} \biggl| \frac{1}{n} \sum_{i=1}^n \sigma_i f(x_i) \biggr| \biggr] \newline &\leq \E \biggl[ \sup_{\|f\|_2 \leq \sqrt{d} \varepsilon_n} \sum_{j=1}^d \sup_{\|g\|_2 \leq \|g_j\|_2} \biggl| \frac{1}{n} \sum_{i=1}^n \sigma_i g(x_i) \biggr| \biggr] \, . \end{align} If \(\| g_j \|_2 \leq \varepsilon_n\), bound by \(\| g_j \|_2\) by \(\varepsilon_n\); otherwise \(\varepsilon_n / \| g_j \|_2 \leq 1\) so \begin{align} \sup_{\|g\|_2 \leq \|g_j\|_2} \biggl| \frac{1}{n} \sum_{i=1}^n \sigma_i g(x_i) \biggr| &= \frac{\| g_j \|_2}{\varepsilon_n} \sup_{\|g\|_2 \leq \|g_j\|_2} \biggl| \frac{1}{n} \sum_{i=1}^n \sigma_i \frac{\varepsilon_n}{\| g_j \|_2} g(x_i) \biggr| \newline &\leq \frac{\| g_j \|_2}{\varepsilon_n} \sup_{\|g\|_2 \leq \varepsilon_n} \biggl| \frac{1}{n} \sum_{i=1}^n \sigma_i g(x_i) \biggr| \, , \end{align} by the star-shaped property of \(\G\). Therefore \begin{align} \sum_j \sup_{\|g\|_2 \leq \|g_j\|_2} \biggl| \frac{1}{n} \sum_{i=1}^n \sigma_i g(x_i) \biggr| \leq \biggl( d + \sum_j \frac{\|g_j\|_2}{\varepsilon_n} \biggr) \sup_{\|g\|_2 \leq \varepsilon_n} \biggl| \frac{1}{n} \sum_{i=1}^n \sigma_i g(x_i) \biggr| \, , \end{align} where \begin{align} \sum_j \frac{\|g_j\|_2}{\varepsilon_n} \leq \frac{\sqrt{d}}{\varepsilon_n} \biggl( \sum_j \| g_j \|_2^2 \biggr)^{1/2} = \frac{\sqrt{d}}{\varepsilon_n} \|f\|_2 \leq d \, . \end{align} Here the equality follows from that, for \(i \neq j\), \(\langle g_i , g_j \rangle_2 = \E[g_i (x_i)] \E[g_j(x_j)] = 0\) because the coordinates of \(x\) are pairwise independent, and the functions are centred. We thus have the desired result \begin{align} \bar{\Rc}(\sqrt{d} \varepsilon_n ; \F) \leq 2 d \bar{\Rc}_n (\varepsilon_n ; \G) \leq 2 d \varepsilon_n^2 \, . \end{align}