Let $g: \mathbb{R} \rightarrow \mathbb{R}$ be an unknown function, twice continuously differentiable with $\left|g^{\prime \prime}(x)\right| \leqslant M$ for all $x \in \mathbb{R}$. For some $x_{0} \in \mathbb{R}$, we know the value $g\left(x_{0}\right)$ and we wish to estimate its derivative $g^{\prime}\left(x_{0}\right)$. To do so, we have access to a pseudo-random number generator that gives $U_{1}^{*}, \ldots, U_{N}^{*}$ i.i.d. uniform over $[0,1]$, and a machine that takes input $x_{1}, \ldots, x_{N} \in \mathbb{R}$ and returns $g\left(x_{i}\right)+\varepsilon_{i}$, where the $\varepsilon_{i}$ are i.i.d. $\mathcal{N}\left(0, \sigma^{2}\right)$.

(a) Explain how this setup allows us to generate $N$ independent $X_{i}=x_{0}+h Z_{i}$, where the $Z_{i}$ take value 1 or $-1$ with probability $1 / 2$, for any $h>0$.

(b) We denote by $Y_{i}$ the output $g\left(X_{i}\right)+\varepsilon_{i}$. Show that for some independent $\xi_{i} \in \mathbb{R}$

$$Y_{i}-g\left(x_{0}\right)=h Z_{i} g^{\prime}\left(x_{0}\right)+\frac{h^{2}}{2} g^{\prime \prime}\left(\xi_{i}\right)+\varepsilon_{i}$$

(c) Using the intuition given by the least-squares estimator, justify the use of the estimator $\hat{g}_{N}$ given by

$$\hat{g}_{N}=\frac{1}{N} \sum_{i=1}^{N} \frac{Z_{i}\left(Y_{i}-g\left(x_{0}\right)\right)}{h}$$

(d) Show that

$$\mathbb{E}\left[\left|\hat{g}_{N}-g^{\prime}\left(x_{0}\right)\right|^{2}\right] \leqslant \frac{h^{2} M^{2}}{4}+\frac{\sigma^{2}}{N h^{2}} .$$

Show that for some choice $h_{N}$ of parameter $h$, this implies

$$\mathbb{E}\left[\left|\hat{g}_{N}-g^{\prime}\left(x_{0}\right)\right|^{2}\right] \leqslant \frac{\sigma M}{\sqrt{N}}$$