Exercise 14.11: Bounds on Histogram Density Estimation
Consider the minimisation of $\norm{f - f^*}_2^2$ over $f = \sum_{m=1}^T \beta_m \phi_m$ where $\beta \in \R^T$ is such that $\norm{\beta}_1 = 1$. First, we omit the constraint that $\norm{\beta}_1 = 1$, perform the unconstrained optimisation, and show that the constraint actually holds at the optimum, which means that we also solved the constrained problem. Without the constraint, using $L^2[0, 1]$-orthonormality of $(\phi_m)_{m=1}^T$, it follows that $\beta^*_m = \lra{f^*, \phi_m}_2 \ge 0$. Therefore, \begin{equation} \norm{\beta^*}_1 = \sum_{m=1}^T \lra{f^*, \phi_m}_2 = \lra{f^*, 1}_2 = 1, \end{equation} because $f^*$ is a density on $[0, 1]$ and hence integrates to one. Next, using $1$-Lipschitz continuity of $f^*$, for any $m \in [T]$ and $x \in (m - 1, m]/T$, it is true that \begin{equation} |f(x) - f^*(x)| = |f^*(x) - \lra{f^*, \phi_m}_2| \le \frac{1}{T}. \end{equation} Therefore, $\inf_{f \in \F} \norm{f - f^*}_2^2 \le 1/T^2$. For the critical radius, the usual parametric rate applies: $\delta^2_n \propto T/n$. Setting $T \propto n^{1/3}$ in Corollary 14.24 then gives the result.