Let $f:\mathbb R^d \to \mathbb R$ be a "sufficiently smooth" function. For simplicity, we may consider $f$ to be an affine function, i.e $f(x) \equiv b-x^\top w$, for some $(w,b) \in \mathbb R^{d}$. Let $\Phi:\mathbb R \to (0,1)$ be the standard Gaussian CDF defind by
$$
\Phi(t):= \frac{1}{\sqrt{2\pi}}\int\_{-\infty}^t e^{-s^2/2}\,dx,
$$
and let $\theta:\mathbb R \to \mathbb R$ be a the Heaviside unit-step funciton defined by


$$
\theta (t) = \begin{cases}
0,&\mbox{ if }t < 0,\\
1/2,&\mbox{ if }t = 0,\\
1,&\mbox{ if }t>0.
\end{cases}
$$


Define a scalar $s \in [0,1]$ by


$$
s:= \mathbb E\_X[\theta(f(X))] = \mathbb P(f(X)>0).
$$


Now, let $X$ be a random variable on $\mathbb R^d$ with "sufficiently smooth" probability density function $\rho$, and let $X\_1,\ldots,X\_n$ be $n$ iid copies of $X$. Given a bandwidth parameter $h=h\_n > 0$, define the random variable $\hat{s}\_{n,h} \in (0,1)$ by


$$
\hat{s}\_{n,h} := \frac{1}{n}\sum\_{i=1}^n\Phi\left(\frac{f(X\_i)}{h}\right).
$$


Finally, define the random variable $\Delta \in [0, 2)$ by


$$
\Delta\_{n,h} := |\hat{s}\_{n,h} - s|.
$$


Intuitively, one would expect "$\Delta\_{n,h} \to 0$" in the limit when $n \to \infty$ such that $h \to 0$ and $nh^d \to \infty$. My goal is to quantify this convergence by upper-bounding $\Delta\_{n,h}$, by a deterministic quantity $\varepsilon\_{n,h}$ which goes to zero.



> 
> **Question 1.** *Is it possible to give good quantitative upper-bounds for $\Delta\_{n,h}$, in terms of $n$ and $h$?, which are valid with high-probability over the $X\_i$'s ?*
> 
> 
> 



> 
> **Question 2.** *Is it even true that $\Delta\_{n,h} \to 0$ ?*
> 
> 
> 



Bound error in approximating $E_x [H(f(x))]$ with random $(1/n) \sum_{i=1}^n \Phi(f(x_i)/h)$ where $H$ is Heaviside function and $\Phi$ is normal CDF
$\newcommand{\si}{\sigma}$Let
\begin{equation\*}
 Y:=f(X),\quad Y\_i:=f(X\_i), 
\end{equation\*}
so that $Y,Y\_1,Y\_2,\dots$ are iid real-valued random variables (r.v.'s).


Assume that (i) the r.v. $Y$ has a density $p\_Y$ continuous at $0$ and (ii) $E|Y|^k<\infty$ for some real $k>0$. Except possibly for entering indirectly into these two conditions -- (i) and (ii), the dimension $d$ or any further specifics concerning $X$ and $f$ will play no role in what follows.


Indeed, then
\begin{equation\*}
 s=P(Y>0),
\end{equation\*}
\begin{equation\*}
 \hat s\_{n,h}=\frac1n\sum\_{i=1}^n\Phi(Y\_i/h),
\end{equation\*}
\begin{equation\*}
 E\hat s\_{n,h}=E\Phi(Y/h)=:\mu\_h. 
\end{equation\*}


Let $n\to\infty$ and $h\downarrow0$. Then $\Phi(Y/h)\to1(Y>0)$ in probability and hence, by dominated convergence,
\begin{equation\*}
\begin{aligned}
 \mu\_h=E\Phi(Y/h)&\to p:=P(Y>0),\\ 
 \si^2\_h:=Var\,\Phi(Y/h)&\to pq,\\ 
 a\_h:=E|\Phi(Y/h)-\mu\_h|^3&\to pq(p^2+q^2),
\end{aligned}
\end{equation\*}
where $q:=1-p$; without loss of generality, $0<p<1$.
By the Berry--Esseen inequality, for all real $z\ge0$,
\begin{equation\*}
 P\Big(\Big|\frac{\hat s\_{n,h}-\mu\_h}{\si\_h/\sqrt n}\Big|>z\Big)
 \le2(1-\Phi(z))+\frac{a\_h/\si\_h^{3/2}}{2\sqrt n},
\end{equation\*}
whence
\begin{equation\*}
 |\hat s\_{n,h}-\mu\_h|=O\_P(1/\sqrt n). \tag{1}\label{1}
\end{equation\*}


Let real $c>0$ vary so that $c\to\infty$ but $ch\to0$. Then
\begin{equation\*}
\begin{aligned}
 |\mu\_h-s|&\le E|\Phi(Y/h)-1(Y>0)| \\ 
 &\le P(|Y|<ch)+(1-\Phi(c))P(|Y|\ge ch) \\ 
 &\lesssim 2p\_Y(0)ch+e^{-c^2/(2+o(1))} \frac{E|Y|^k}{(ch)^k}. 
\end{aligned} 
\end{equation\*}
Choosing now $c$ more specifically, so that $c\sim\sqrt{(2k+1)\ln\frac1h}$, we get
\begin{equation\*}
 |\mu\_h-s|=O\big(h\sqrt{\ln\tfrac1h}\big).
\tag{1'}\label{1'} 
\end{equation\*}
Thus, in view of \eqref{1} and \eqref{1'},  

\begin{equation\*}
 |\hat s\_{n,h}-s|=O\_P\Big(\frac1{\sqrt n}+h\sqrt{\ln\frac1h}\Big), 
\tag{2} 
\end{equation\*}
as $n\to\infty$ and $h\downarrow0$.


