Deviation in $\sup$-norm of simple fixed design NW-regression estimator For some unknown $(H,\alpha)$-Hölder function $f:[0,1]\rightarrow\mathbb{R}$, we observe
$$Y_i=f(x_i)+\varepsilon_i,$$
where $x_i=i/n$, $n\in\mathbb{N}$, $i\in\{1,2,\ldots,n\}$, with iid centered Gaussian $\epsilon_i$ with $\operatorname{Var}[\varepsilon_1]=\sigma^2<\infty$.
Now we consider the Nadaraya-Watson kernel estimator for $f$ with the simple Kernel $K(x)=\mathbb{I}_{[-1,1]}(x)$ and bandwidth $h\geq 2/n$, i.e. for $x\in[0,1]$
$$\widehat{f}(x)=\sum_{i=1}^n Y_i\cdot W_{i,h}(x), \text{ where } W_{i,h}(x) = \frac{K((x-x_i)/h)}{\sum_{j=1}^n K((x-x_j)/h)}.$$
Now you typically consider pointwise bias and variance of the estimator - through some computation and Gaussian concentration that leads to
$$\mathbb{P}\left(|\widehat{f}(x)-f(x)|> H\cdot h^\alpha+\sqrt{\frac{4\sigma^2}{nh}\ln(2/\delta)}\right)\leq\delta$$
for any $x\in[0,1]$ and $\delta\in(0,1)$.
Now I would like to derive a result of the form
$$\mathbb{P}\left(\Vert\widehat{f}-f\Vert_{\infty}> H\cdot h^\alpha + \sqrt{\frac{4\sigma^2}{nh}\ln(2n/\delta)}\right)\leq\delta.$$
Clearly, there is a union bound over $i$ included, so I start by
\begin{eqnarray*}
\{\Vert\widehat{f}-f\Vert_\infty >c\}&\subseteq&\bigcup_{i=1}^n\{\exists u \in [0,1/n) : |\widehat{f}(x_i-u)-f(x_i-u)|\geq c\}.
\end{eqnarray*}
I need a way to completely get rid of $u$, but I don't see the trick... I thought the most promising start would be
$$|\widehat{f}(x_i-u)-f(x_i-u)|\leq |\widehat{f}(x_i-u)-\widehat{f}(x_i)| + |\widehat{f}(x_i)-f(x_i)|+|f(x_i)-f(x_i-u)|.$$
Then I can handle the last two expressions, but how can I bound/identify the first expression
$$\widehat{f}(x_i-u)-\widehat{f}(x_i)=\sum_{j=1}^n (f(x_j)+\varepsilon_j)(W_{j,h}(x_i-u)-W_{j,h}(x_i))$$
as a kind of Gaussian rv independently of $u$? Since $u< 1/n$, the two weight functions there won't be far apart, but can I quantify this nicely?
 A: The key observation here is that, as a function of $x$, $$g(x):=\widehat{f}(x)-\mathbb{E}[\widehat{f}(x)]=\sum_{i=1}^n \varepsilon_i W_{i,h}(x)$$ can only take a finite number of values.
More precisely, each $x\in[0,1]$ can be written as $x=x_i-u$ for some $i\in\{1,2,\ldots,n\}$ and $u\in[0,\frac{1}{n}]$. Now, if you shift the window $[x_i-h,x_i+h]$ to $[x_{i-1}-h,x_{i-1}+h]$ (with $x_{i-1}:=0$) through $[x_i-h-a,x_i+h-a]$, $a\in[0,\frac{1}{n}]$, clearly the weight $W_{i,h}(x)$ changes at most two times - the first time corresponds to some $a\leq\frac{1}{2n}$ and the second time corresponds to some $a\geq\frac{1}{2n}$. In fact, all weights $W_{k,h}(x)$ have at most these two change points and therefore
$$g(x_i-u)\in\left\{g(x_{i-1}),g\left(\frac{x_{i-1}+x_i}{2}\right),g(x_i)\right\}.$$
Using that for any $x\in[0,1]$, $|\mathbb{E}[\widehat{f}(x)]-f(x)|\leq H\cdot h^\alpha$, we can now derive the desired deviation bound:
\begin{eqnarray*}
\mathbb{P}(\Vert \widehat{f}-f\Vert_{\infty}>c)&\leq& \mathbb{P}\left(\exists x\in[0,1]:~|g(x)|+H\cdot h^\alpha>c\right)\\
&\leq&\sum_{k=0}^{2n}\mathbb{P}\left(\left|g\left(\frac{k}{2n}\right)\right|+H\cdot h^\alpha>c\right)\\
&\stackrel{!}{\leq}&\delta.
\end{eqnarray*}
With the Gaussian deviation result used above, we see that $c=\sqrt{\frac{4\sigma^2}{nh}\ln\left(\frac{2(2n+1)}{\delta}\right)}$ is a sufficient choice (replace $\delta$ by $\frac{\delta}{2n+1}$), i.e. for any $\delta\in(0,1)$
$$\mathbb{P}\left(\Vert \widehat{f}-f\Vert_{\infty}>H\cdot h^\alpha+\sqrt{\frac{4\sigma^2}{nh}\ln\left(\frac{2(2n+1)}{\delta}\right)}\right)\leq\delta$$
