= Solution
On a grid $G\subset[-L,L]$ with mesh proportional to $\varepsilon$, <Hoeffding inequality> and a union bound give
$$
\mathbb P\left(\max_{x,y\in G}|k(x,y)-\phi(x)^T\phi(y)|>\varepsilon/2\right)
\leq C\frac{L^2}{\varepsilon^2}e^{-c\ell\varepsilon^2}.
$$
The density of $W$ has exponential tails. A <Chernoff bound> therefore shows that $\ell^{-1}\sum_i|W_i|$ is bounded by an absolute constant except on an event of probability $e^{-c'\ell}$. On that event, both the empirical kernel and $k$ are uniformly Lipschitz, so every pair $(x,y)$ is approximated by its nearest grid pair with total error at most $\varepsilon/2$. Enlarging constants and using $0<\varepsilon\leq1$ yields
$$
\mathbb P\left(\sup_{x,y\in[-L,L]}|k(x,y)-\phi(x)^T\phi(y)|\geq\varepsilon\right)
\leq\frac{C_1L^2}{\varepsilon^2}e^{-C_2\ell\varepsilon^2}.
$$
Back to article page
