We have learnt KNN for classification. In fact, KNN can also be used for regression tasks. For a

pair data $(x_i,y_i)$ the optimal regression function is $Y=f(x)+lon,$ where the noise $lon$ has a mean

$E(e|x)=0$ and a variance Var$(e|x_i)=(x_i).$ We select the squared error loss as the risk, that is

$E((Y-(hat(f))(x){)}^2)$

The K$-$nearest neighbor estimate the regression is average the $k$ nearest neighbor values

hat$(f)(x)=\frac{1}{k}{\displaystyle \underset{i=1}{\overset{K}{}}}{y}_{NN(x,i)}$

we denote $NN(x,i)$ as the index of the $i^{th}$ nearest neighbor of $x.$

$(1)$ Let us consider the simplest setting, no noise and $k=1.$ If the data size $n$ tends to infinity, does the risk tend to $0?$ If yes, please

provide a proof. If not, please specify the value of the risk.

$(2)$ When we consider noises and $k$ nearest neighbor, does the risk tend to $0?$ If yes, please provide a proof. If not, please specify the

value of the risk.

$(3)$ For KNN$,$ assuming data $x$ follows a probability density function $g(x),$ please provide the upper bound of the distance from $x$ to the

k$-$nearest neighbor $x_{NN}$ as $n$ tends to infinity