4
$\begingroup$

Let $\Theta$ be an open subset of some $\mathbb R^m$ and let $P$ be a probability distribution on $\mathbb R^d$ with density $f$ in a Sobolev space $W_p^s(\mathbb R^d)$, i.e all derivatives of $f$ upto and including order $s$ exist and are bounded in $L_p$ norm, for some fixed $s\ge 1$ and $1 \le p \le \infty$. Let $\ell:\mathbb R^d \times \mathbb R^m \to \mathbb R$ be a measurable function, and consider a risk criterion $c_f: \Theta \rightarrow \mathbb R$, defined by $$ c_f(\theta) = \int_{\mathbb R^d}\ell(x,\theta)f(x)\,dx = \mathbb E_{X \sim P} [\ell(X,\theta)]. $$ Given an iid sample $X_1,\ldots,X_n$ from $f$ (i.e., from the corresponding distribution $P$), let $$ \hat{f}_{n,h}= \frac{1}{n}\sum_{i=1}^n K_h(\cdot - X_i) $$ be the kernel density estimate (KDE) for $f$ with bandwidth $h>0$ and Gaussian kernel $$ K_h(z) := \dfrac{e^{-\|z\|^2/(2h^2)}}{(2\pi h^2)^{d/2}}. $$ For an appropriate choice of bandwidth $h=h_n$, classical KDE theory gives us the following approximation valid for $1 < p \le \infty$, $$ \mathbb E_S\,\|\hat{f}_{n,h}-f\|_{L^p}^p := \int_{\mathbb R^d}|\hat{f}_{n,h}(x)-f(x)|^p\,dx \lesssim n^{-sp/(2s+d)}, \tag{1}\label{1} $$

where the expectation is over $S := \{X_1,\ldots,X_n\}$.

Let $\hat{\theta}_{n,h}$ minimize $c_{\hat{f}_{n,h}}(\theta)$ over $\theta \in \Theta$ and let $$ R_{n,h} := c_f(\hat{\theta}_{n,h})-\inf_\theta c_f(\theta) = \sup_\theta c_f(\hat{\theta}_{n,h}) - c_f(\theta), $$ be the associated regret.

Question. What are minimal conditions on the loss function $\ell$ which ensure that $R_{n,h} \lesssim \varepsilon_n$ holds for some $\varepsilon_n \to 0$ with high probability over the $X_i$'s ? Furthermore, when is it possible to have $\varepsilon_n \lesssim n^{-\beta}$, for some constant $\beta>0$ and some choice of bandwidth $h=h_n$ ?

Observations

Note that one always has the following Bias-Variance decomposition $$ R_{n,h} \le \underbrace{\|\mathbb E_S \, c_{\hat{f}_{n,h}}-c_f\|_\infty}_{\text{Bias}} + \underbrace{\|c_{\hat{f}_{n,h}}-\mathbb E_S\,c_{\hat{f}_{n,h}}\|_\infty}_{\text{Variance}}, $$ where $\|u\|_\infty := \inf_{\theta \in \Theta}|u(\theta)|$.

The Bias term. Now, if we make the following "sloppy" assumption

The loss function $\ell$ is uniformly-bounded in $\theta$ and w.r.t $f$, in the sense that $$ \|\ell(x,\cdot)\|_\infty := \sup_{\theta \in \Theta}|\ell(x,\theta)| \le |g(x)|, $$ for all $x \in \mathbb R^d$, and some nonnegative function $g \in L^q$ with $1/p+1/q = 1$,

then it's easy to see via the Cauchy-Schwarz inequality that, the bias term can be bounded like so $$ \begin{split} \|\mathbb E_{S} c_{\hat{f}_{n,h}}-c_f\|_\infty &\le \sup_{\theta}\int_{\mathbb R^d} |\ell(x,\theta)|\cdot\mathbb E_S|\hat{f}_{n,h}(x)-f(x)|\,dx\\ &\le \|g\|_{L^q}\cdot \mathbb E_S\|\hat{f}_{n,h}-f\|_{L^p}\\ & \lesssim (\mathbb E_S\|\hat{f}_{n,h}-f\|_{L^p}^p)^{1/p}. \end{split} $$ Thus, for the choice of bandwidth $h=h_n$ which ensures \eqref{1}, we obtain the following upper bound for the bias term,

$$ \|\mathbb E_S\,c_{\hat{f}_{n,h}}-c_f\|_\infty \lesssim n^{-s/(2s+d)} = o(1). $$

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.