0.20 Lower performance bounds for estimators  (Page 4/4)

Now $p_{Y|X}^{\left(1\right)}(Y_1=1|X_1)=1/2+a$ and $p_{Y|X}^{\left(0\right)}(Y_1=1|X_1)=1/2-a$ . Also under model 1, $Y_1\sim \text{Bernoulli}(1/2+a)$ . So we get:

Let $a=1/\sqrt{n}$ and $n\ge 16$ , then $K(P_1\left|\right|P_0)\le 4n\frac{1}{n}\frac{1}{1/2-1/\sqrt{n}}\le 16$ .

Using Theorem 1 , since $d_{\Delta }(G_0^{*},G_1^{*})=1$ , we get:

Taking $s_n=1/\sqrt{n}$ , this implies

or, after Markov's inequality

Therefore, apart from the $logn$ factor, ERM is getting the best possible performance.

Reducing the initial problem to a binary hypothesis testing does not always work. Sometimes we need $M$ hypotheses, with $M\to \infty$ as $n\to \infty$ . If this is the case, we have the following theorem:

Theorem 2 Let $M\ge 2$ . $\{f_0,\cdots ,f_M\}\in \mathcal{F}$ be such that

• . $d(f_j,f_k)\ge 2s_n$ , where $d$ is a semi-distance.
• . $\frac{1}{M}{\sum }_{j=1}^{M}K(P_j\left|\right|P_0)\le \alpha logM$ , with $0<\alpha <1/8$ .

Then

We will use this theorem to show that the estimator of Lecture 4 is optimal. Recall the setup of Lecture 4 . Let

i.e. the class of Lipschitz functions with constant $L$ . Let

$\mathbb{E}\left[W_i\right]=0,\mathbb{E}\left[W_i^2\right]={\sigma }^2<\infty ,W_i,W_j\text{are}\text{indepedent}\text{if}i\ne j$ . In that lecture, we constructed an estimator ${\widehat{f}}_n$ such that

Is this the best we can do?

We are going to construct a collection $f_0,\cdots ,f_M\in \mathcal{F}$ and apply Theorem 2. Notice that the metric of interest is $d({\widehat{f}}_n,f)=\left|\right|{\widehat{f}}_n-f\left|\right|$ , a semi-distance. Let $W_i\stackrel{iid}{\sim }\mathcal{N}(0,{\sigma }^2)$ . Let $m\in \mathbb{N}$ , $h=1/m$ and define

Note that $\left|K\right(a)-K(b\left)\right|\le L|a-b|$ , $\forall a,b$ . The subclass we are going to consider are functions of the form

i.e. “bump" functions. Let $\Omega ={\{0,1\}}^m$ be the collection of binary vectors of length $m$ , e.g. $w=(1,0,1,\cdots ,0)\in \Omega$ . Define

Note that for $w,w^{\text{'}}\in \Omega$ ,

where $\rho (w,w^{\text{'}})$ is the Hamming distance, $\rho (w,w^{\text{'}})={\sum }_{i=1}^m|w_i-w_i^{\text{'}}{|}^2={\sum }_{i=1}^m|w_i-w_i^{\text{'}}|$ . Now

so

Since $\left|\Omega \right|=2^n$ , the number of functions in our class is $2^n$ . Turns out, we do not need to consider all functions $f_w,w\in \Omega$ , but only a select few. Using all the functions leads to a looser lower bound of the form $n^{-1}$ , which corresponds to the parametric rate. The problem under consideration is non-parametric, and hence we expecta slower rate of convergence. To get a tighter lower bound, the following result is of use:

Varshamov-gilbert '62

Let $m\ge 8$ . There exists a subset $\{w^{\left(0\right)},\cdots ,w^{\left(M\right)}\}$ of $\Omega$ such that $w^{\left(0\right)}=(0,0,\cdots ,0)$ ,

What this lemma says is that there are many $(\sim 2^m)$ sequences in $\Omega$ that are very different (i.e. $\rho (w^{\left(j\right)},w^{\left(k\right)})\sim m$ ). We are going to use the lemma to construct a useful set of hypotheses. Let $\{w^{\left(0\right)},\cdots ,w^{\left(M\right)}\}$ be the class of sequences in the lemma and define

We now need to look at the conditions of Theorem 2 and choose $m$ appropriately.

First note that for $j\ne k$ ,

Now let $P_j\stackrel{\Delta }{=}{P}_{Y_1,\cdots ,Y_m}^{\left(j\right)},j\in \{0,\cdots ,M\}$ . Then

Now notice that $logM\ge \frac{m}{8}log2$ (from Lemma [link] ). We want to choose $m$ such that

This gives

so take $m=\lfloor C_0{n}^{1/3}+1\rfloor$ . Now

Therefore,

or,

or after Markov's inequality,

Therefore, the estimator constructed in class attains the optimal rate of convergence.