Exercise 2.15: Concentration and Kernel Density Estimation

bounded differences inequality chapter 2

We show that \begin{equation} g(x_1, \ldots, x_n) = \norm{\hat f_n - f}_1 \end{equation} has bounded differences, where \(\hat f_n\) is the KDE for observations \(x_1,\ldots,x_n\). This follows directly from the reverse triangle inequality: \begin{align} \abs{g(x, x_2,\ldots, x_n) - g(y, x_2, \ldots, x_n)} &\le \norm{\hat f_n(x) - \hat f_n(y)}_1 \newline &= \frac{1}{nh} \int \abs{ K\parens{\frac{z - x}{h}} - K\parens{\frac{z - y}{h}} } \isd z \newline &\le \frac{2}{n}\norm{K}_1 = \frac{2}{n}. \end{align} Therefore, by the Bounded differences inequality, \begin{equation} \P(\norm{\hat f_n - f}_1 - \E[\norm{\hat f_n - f}_1] \ge t) \le e^{-\frac12 n t^2}. \end{equation}