2 8 1 Orthogonal Design

2.8.1. Orthogonal Design

We consider the linear model $Y=f^{*}+\epsilon=X\beta^{*}+ \epsilon$ in the coordinate-sparse setting. We assume that the columns of X are orthogonal.

A. Hard thresholding

1. We consider $\mathscr{M}=\mathscr{P}([\![1,p]\!] )$, $\{ S_m, m \in \mathscr{M} \}$ a collection of linear subspaces of $\mathbb{R}^n$ and, for $m \in \mathscr{M}$, $P_{S_m}$ the orthogonal projection operator onto $S_m$.
In this setting, with $X_j$ the j-th column of X, the criterion $\|Y-P_{S_m}Y\|^2$ is equal to:
$\|Y\|^2 - 2<Y,P_{S_m}Y> + \|P_{S_m}Y\|^2$

As $P_{S_m}$ is a projection, $P_{S_m}=P_{S_m}^2=P_{S_m}^TP_{S_m}$
Thus the scalar product is written $<Y,P_{S_m}Y>=Y^TP_{S_m}Y=Y^TP_{S_m}^TP_{S_m}Y= \|P_{S_m}Y\|^2$
Finally, $\|Y-P_{S_m}Y\|^2=\|Y\|^2 - \|P_{S_m}Y\|^2$

$S_m=Span\{X_i, \space i \in m\}$ and columns of X are orthogonal so $\{\frac{X_i}{\|X_i\|}, \space i \in m\}$ is an orthonormal basis of $S_m$. Thus the projection onto $S_m$ can be written as $P_{S_m}Y=\sum\limits_{j \in m} \frac{<Y,X_j> }{\|X_j\|^2} X_j$, and $\| P_{S_m}Y\|^2=\sum\limits_{j \in m} \left( \frac{X_j^TY} {\|X_j\|}\right)^2$.
Moreover $pen(m)\sigma^2=\lambda|m|\sigma^2=\sum\limits_{j \in m}\lambda\sigma^2$

We finally have : $\boxed{ \|Y-P_{S_m}Y\|^2 + pen(m)\sigma^2 = \|Y\|^2 + \sum\limits_{j \in m} \left( \lambda\sigma^2 - \left( \frac{X_j^TY}{\|X_j\|}\right)^2\right).}$

2. $\hat{m}_{\lambda} \in \underset{m \in M}{Argmin} \{ \|Y-P_{S_m}Y\|^2 + pen(m)\sigma^2\}$ i.e. $\hat{m}_{\lambda} \in\underset{m \in M}{Argmin} \left\{ \|Y\|^2 + \sum\limits_{j \in m} \left( \lambda\sigma^2 - \left( \frac{X_j^TY}{\|X_j\|}\right)^2\right) \right\}$
As $\|Y\|^2$ is invariant, only the second part needs to be minimized. And the best way to do it is to select only the strictly negative terms of the sum :

$\boxed{ \hat{m}_{\lambda}=\{j \space | \space (X_j^TY)^2>\lambda\|X_j\|^2\sigma^2.}$

3. The calculation of the term " $(X_j^TY)^2>\lambda\|X_j\|^2\sigma^2$" for all $j \in [\![1,p]\!]$ is linear in $p$ whereas
"$\|Y-P_{S_m}Y\|^2 + pen(m)\sigma^2$ "for all $m\in \mathscr{P}([\![1,p]\!] )$ makes $2^p$ (cardinal of $\mathscr{P}([\![1,p]\!] )$) calculus.

$\boxed{\text{The computational complexity in p of the criterion, that was exponential, is now linear in p.}}$

B. Minimal penalties

We assume in this part that $f^{*}=0$ so that the oracle model $m_0$ is the void set.

1. Let us fix some $j \in [\![1,p]\!],\text{ and set}\space Z_j=\frac{X_j^T\epsilon}{\|X_j\|\sigma}$
We first prove that $Z_j$ follows a standard normal distribution :
$\epsilon \sim \mathscr{N}(0,\sigma^2I_n) \text{ so } X_j^T\epsilon \sim \mathscr{N}(0,X_j^T\sigma^2I_nX_j) \text{ and } \frac{X_j^T\epsilon}{\|X_j\|\sigma} \sim \mathscr{N}(0,\frac{\sigma^2\|X_j\|^2}{(\sigma\|X_j\|)^2})$

We finally have $Z_j \sim \mathscr{N}(0,1)$.

Let us fix some $(i,j) \in [\![1,p]\!]^2,$
$cov(Z_i,Z_j)=\frac{1}{\|X_j\|\|X_i\|\sigma^2}cov(X_j^T\epsilon,X_i^T\epsilon)=\frac{1}{\|X_j\|\|X_i\|\sigma^2}X_j^Tcov(\epsilon,\epsilon)X_i=\frac{1}{\|X_j\|\|X_i\|}<X_i,X_j> I_d$
As X is orthogonal, $cov(Z_i,Z_j)=0$, id est $Z_j$ and $Z_i$ are independent when $i \ne j$.

$\boxed{ \text{The }Z_j \text{ are i.i.d with } \mathscr{N}(0,1) \text{ distribution.} }$

2. $\hat{m}_{\lambda}=\{j \space | \space (X_j^TY)^2>\lambda\|X_j\|^2\sigma^2 \}=\{ j \space | \space \left( \frac{X_j^TY}{\|X_j\|\sigma}\right) ^2>\lambda\}$
Since $Y=f^*+\epsilon=\epsilon$, for all $j \in [\![1,p]\!], \space \left( \frac{X_j^TY}{\|X_j\|\sigma}\right)^2=\left( \frac{X_j^T\epsilon}{\|X_j\|\sigma}\right)^2=Z_j^2$

Thus $\hat{m}_{\lambda}= \{j \space | \space Z_j^2 > \lambda \}$ and $|\hat{m}_{\lambda}|=\sum \limits_{j=1}^{p} \mathbb{1}_{\{Z_j^2>\lambda\}}$.
As the $Z_j$ are independent and there are $p$ terms in the sum : $\boxed{|\hat{m}_{\lambda}|\sim \mathscr{B}(p, \mathbb{P}(Z^2>\lambda)=\eta_{\lambda})\text{ with }Z \sim \mathscr{N}(0,1).}$

3. The AIC criterion is defined by :
$\hat{m}_{AIC} \in \underset{m \in M}{Argmin} \{ \|Y-\hat{f}_m\|^2 + 2d_m\sigma^2\}$ with, for $m \in M \space \hat{f}_m=P_{S_m}Y$ and $d_m=|m|$

So $\mathbb{E}[|\hat{m}_{AIC}|]=p\mathbb{P}(Z^2>2)$ with $Z \sim\mathscr{N}(0,1)$
As (the numerical value was found in a table of quantiles of standard normal distribution) $\mathbb{P}(Z^2>2)=\mathbb{P}(Z<-\sqrt{2})+\mathbb{P}(Z>\sqrt{2}))=2\mathbb{P}(Z>\sqrt{2}))\approx 0,16.$

Finally, $\boxed{\mathbb{E}[|\hat{m}_{AIC}|]\approx 0,16p.}$ Thus, the AIC criterion is not suited for this context because almost 20 percent of the variables are selected which is too much.

4. $\mathbb{E}[|\hat{m}_{\lambda}|]=p\mathbb{P}(Z^2>\lambda)$ with $\lambda=2K\log{p} \underset{p\to +\infty}{\longrightarrow} +\infty$
Since $\mathbb{P}(Z^2>\lambda) \underset{\lambda\to +\infty}{\sim} \sqrt{\frac{2}{\pi\lambda}} e^{-\frac{\lambda}{2}}$ for $K>0$ we have $\mathbb{E}[|\hat{m}_{2K\log{p}}|] \underset{p\to +\infty}{\sim} p\sqrt{\frac{2}{2\pi K\log{p}}}e^{-\frac{2K\log{p}}{2}}=\frac{p^{1-K}}{\sqrt{\pi K\log(p)}}$

If $K<1$, as $\forall (\beta, \alpha) \in \mathbb{R}^{+*^{2}} \log{p}^{\beta}=\underset{p\to +\infty}{o}(p^{\alpha})$,
$\boxed{\text{The mean size of the selected model } \hat{m}_{2K\log{p}} \text{ grows like a fractional power of p.}}$

We can notice that as X is orthogonal, $rg(X)=p$ so we must have $n\ge p$, so when $p\to +\infty$ we also have $n\to +\infty$.

5. For the BIC criterion : $\hat{m}_{BIC} \in \underset{m \in M}{Argmin} \{ \|Y-\hat{f}_m\|^2 + \sigma^2|m|\log{n}\}$
As $p\sim n$, this case is an application of the previous result with $K=\frac{1}{2}$ and $\mathbb{E}[|\hat{m}_{BIC}|]\underset{p\to +\infty}{\sim}\frac{\sqrt{p}}{\sqrt{\frac{\pi}{2}\log{p}}}$

Finally, $\boxed{\mathbb{E}[|\hat{m}_{BIC}|]\underset{p\to +\infty}{\sim}\sqrt{\frac{2p}{\pi\log{p}}}.}$
As $K=\frac{1}{2}<1$ the BIC criterion is not suited in the context and the mean size of the selected model $\hat{m}_{BIC}$ tend to infinity.

C) Overfitting with K<1

1.

(1)

\begin{eqnarray} ||\hat{f}_{\hat{m}_{\lambda}}-f^{*}||^{2} & = & ||Proj_{S_{\hat{m}_{\lambda}}}Y-f^{*}||^{2}\\ & = & ||Proj_{S_{\hat{m}_{\lambda}}}(f^{*}+\varepsilon)-f^{*}||^{2}\\ & = & ||(Proj_{S_{\hat{m}_{\lambda}}}f^{*}-f^{*})+Proj_{S_{\hat{m}_{\lambda}}}\varepsilon||^{2}\\ & \stackrel{Pythagore}{=} & ||Proj_{S_{\hat{m}_{\lambda}}}f^{*}-f^{*}||^{2}+||Proj_{S_{\hat{m}_{\lambda}}}\varepsilon||^{2} \end{eqnarray}

with

(2)

\begin{align} S_{\hat{m}_{\lambda}}=span\{X_{j},j\in\hat{m}_{\lambda}\} \end{align}

and we assume that the columns of X are orthogonal, so we can write :

(3)

\begin{eqnarray} ||\hat{f}_{\hat{m}_{\lambda}}-f^{*}||^{2} & = & ||f^{*}-\underset{j\in\hat{m}_{\lambda}}{\sum}P_{j}f^{*}||^{2}+||\underset{j\in\hat{m}_{\lambda}}{\sum}P_{j}\varepsilon||^{2}\\ & \stackrel{Pythagore}{=} & ||f^{*}-\underset{j\in\hat{m}_{\lambda}}{\sum}P_{j}f^{*}||^{2}+\underset{j\in\hat{m}_{\lambda}}{\sum||}P_{j}\varepsilon||^{2} \end{eqnarray}

yet :

(4)

\begin{align} \forall j\in[|1,p|],P_{j}\varepsilon=X_{j}^{T}\varepsilon\frac{X_{j}}{||X_{j}||^{2}} \end{align}

so :

(5)

\begin{align} ||P_{j}\varepsilon||^{2}=||X_{j}^{T}\varepsilon\frac{X_{j}}{||X_{j}||^{2}}||^{2}=\frac{(X_{j}^{T}\varepsilon)^{2}}{||X_{j}||^{4}}||X_{j}||^{2}=(\frac{X_{j}^{T}\varepsilon}{||X_{j}|})^{2}=Z_{j}^{2}\sigma^{2} \end{align}

hence :

(6)

\begin{align} ||\hat{f}_{\hat{m}_{\lambda}}-f^{*}||^{2}=||f^{*}-\underset{j\in\hat{m}_{\lambda}}{\sum}P_{j}f^{*}||^{2}+\underset{j\in\hat{m}_{\lambda}}{\sum}Z_{j}^{2}\sigma^{2} \end{align}

But $||f^{*}-\underset{j\in\hat{m}_{\lambda}}{\sum}P_{j}f^{*}||^{2}\geq0$ so we can forget it to lower bound $||\hat{f}_{\hat{m}_{\lambda}}-f^{*}||^{2}$.
Moreover, we have $Z_{j}^{2}\sigma^{2}\geq0$ and $\hat{m}_{\lambda}\backslash m^{*}\subset\hat{m}_{\lambda}$, so $\underset{j\in\hat{m}_{\lambda}}{\sum}Z_{j}^{2}\sigma^{2}\geq\underset{j\in\hat{m}_{\lambda}\backslash m^{*}}{\sum}Z_{j}^{2}\sigma^{2}$
then :

(7)

\begin{align} ||\hat{f}_{\hat{m}_{\lambda}}-f^{*}||^{2}=||f^{*}-\underset{j\in\hat{m}_{\lambda}}{\sum}P_{j}f^{*}||^{2}+\underset{j\in\hat{m}_{\lambda}}{\sum}Z_{j}^{2}\sigma^{2}\geq\underset{j\in\hat{m}_{\lambda}\backslash m^{*}}{\sum}Z_{j}^{2}\sigma^{2} \end{align}

In one hand, $\underset{j\in\hat{m}_{\lambda}\backslash m^{*}}{\sum}Z_{j}^{2}\sigma^{2}$ has at least $|\hat{m}_{\lambda}|-D^{*}$ terms.

In the other hand, according to A)2) : $\hat{m}_{\lambda}=\{j|(X_{j}^{T}Y)^{2}>\lambda||X_{j}||^{2}\sigma^{2}\}$.
But, for $j\in\hat{m}_{\lambda}\backslash m^{*}$ : $X_{j}^{T}Y=X_{j}^{T}(f^{*}+\epsilon)=X_{j}^{T}f^{*}+X_{j}^{T}\epsilon=0+X_{j}^{T}\epsilon=X_{j}^{T}\epsilon$.
So we obtain that : $\forall j\in\hat{m}_{\lambda}\backslash m^{*},\,Z_{j}>\lambda.$

And finally :

(8)

\begin{align} \boxed{||\hat{f}_{\hat{m}_{\lambda}}-f^{*}||^{2}=||f^{*}-\underset{j\in\hat{m}_{\lambda}}{\sum}P_{j}f^{*}||^{2}+\underset{j\in\hat{m}_{\lambda}}{\sum}Z_{j}^{2}\sigma^{2}\geq\underset{j\in\hat{m}_{\lambda}\backslash m^{*}}{\sum}Z_{j}^{2}\sigma^{2}\geq(|\hat{m}_{\lambda}|-D^{*})\lambda\sigma^{2}} \end{align}

2.

Let $a,\,x\in\mathbb{R}^{+}$.

We have, with an integration by substitution ($"z'=z-a"$) :

(9)

\begin{align} \int_{x-a}^{x}e^{-\frac{z^{2}}{2}}dz-\int_{x}^{x+a}e^{-\frac{z^{2}}{2}}dz=\int_{x-a}^{x}e^{-\frac{z^{2}}{2}}-e^{-\frac{(z+a)^{2}}{2}}dz \end{align}

If $a\leq x$, since the exponential and the square functions are nondecreasing on $\mathbb{R}^{+}$, we have $e^{-\frac{z^{2}}{2}}-e^{-\frac{(z+a)^{2}}{2}}\geq0$. And, then,since the integral is nondecreasing, we obtain, if $a\leq x$,
that $\int_{x-a}^{x}e^{-\frac{z^{2}}{2}}-e^{-\frac{(z+a)^{2}}{2}}dz\geq0$ i.e. : $\int_{x-a}^{x}e^{-\frac{z^{2}}{2}}dz\geq\int_{x}^{x+a}e^{-\frac{(z+a)^{2}}{2}}dz$.

Now, assume that $a>x$, i.e. $x-a<0$.

In one hand, we have :

(10)

\begin{eqnarray} \int_{x-a}^{x}e^{-\frac{z^{2}}{2}}dz & = & \int_{x-a}^{0}e^{-\frac{z^{2}}{2}}dz+\int_{0}^{x}e^{-\frac{z^{2}}{2}}dz\\ & \overset{"z'=z"}{=} & \int_{0}^{a-x}e^{-\frac{z^{2}}{2}}dz+\int_{0}^{x}e^{-\frac{z^{2}}{2}}dz\,\,\,\,\,\,\,\,\text{(*)} \end{eqnarray}

In the other hand, again thanks to simple integrations by subtitution
and the nondecreasing of the integral, we can write :

(11)

\begin{align} \int_{x}^{x+a}e^{-\frac{z^{2}}{2}}dz & = & \int_{x}^{a}e^{-\frac{z^{2}}{2}}dz+\int_{a}^{x+a}e^{-\frac{z^{2}}{2}}dz\\ & = & \int_{0}^{a-x}e^{-\frac{(z+x)^{2}}{2}}dz+\int_{0}^{x}e^{-\frac{(z+a)^{2}}{2}}dz\\ & \leq & \int_{0}^{a-x}e^{-\frac{z^{2}}{2}}dz+\int_{0}^{x}e^{-\frac{z^{2}}{2}}dz \end{align}

According to (*) , we have also $\int_{x-a}^{x}e^{-\frac{z^{2}}{2}}dz\geq\int_{x}^{x+a}e^{-\frac{(z+a)^{2}}{2}}dz$ when $a>x$.

And finally :

(12)

\begin{align} \boxed{\forall x,\,a\in\mathbb{R}^{+},\,\,\int_{x-a}^{x}e^{-\frac{z^{2}}{2}}dz\geq\int_{x}^{x+a}e^{-\frac{(z+a)^{2}}{2}}dz} \end{align}

Let $a,x\in\mathbb{R}$. Let $Z$ a standard Gaussian random variable.

• If $a,x\in\mathbb{R}^{+}$ :

In one hand :

(13)

\begin{align} \mathbb{P}((Z+a)^{2}>x^{2}) & = & 1-\mathbb{P}((Z+a)^{2}\leq x^{2})\\ & = & 1-\mathbb{P}(-x-a\leq Z\leq x-a)\\ & = & 1-\int_{-x-a}^{x-a}e^{-\frac{z^{2}}{2}}\frac{dz}{\sqrt{2\pi}}\\ & = & 1-(\int_{-x-a}^{0}e^{-\frac{z^{2}}{2}}\frac{dz}{\sqrt{2\pi}}+\int_{0}^{x-a}e^{-\frac{z^{2}}{2}}\frac{dz}{\sqrt{2\pi}}) \end{align}

And :

(14)

\begin{align} \mathbb{P}(Z^{2}>x^{2}) & = & 1-\mathbb{P}(Z^{2}\leq x^{2})\\ & = & 1-\mathbb{P}(-x\leq Z\leq x)\\ & = & 1-\int_{-x}^{x}e^{-\frac{z^{2}}{2}}\frac{dz}{\sqrt{2\pi}}\\ & \stackrel{symmetry\,of\,the\,Gaussian}{=} & 1-2\int_{0}^{x}e^{-\frac{z^{2}}{2}}\frac{dz}{\sqrt{2\pi}} \end{align}

In the other hand, thanks to the last result :

(15)

\begin{align} \int_{x-a}^{x}e^{-\frac{z^{2}}{2}}dz=\int_{x-a}^{0}e^{-\frac{z^{2}}{2}}dz+\int_{0}^{x}e^{-\frac{z^{2}}{2}}dz\\ & \geq & \int_{x}^{x+a}e^{-\frac{z^{2}}{2}}dz=\int_{x}^{0}e^{-\frac{z^{2}}{2}}dz+\int_{0}^{x+a}e^{-\frac{z^{2}}{2}}dz \end{align}

Then :

(16)

\begin{align} 2\int_{0}^{x}e^{-\frac{z^{2}}{2}}dz\geq\int_{0}^{x-a}e^{-\frac{z^{2}}{2}}dz+\int_{0}^{x+a}e^{-\frac{z^{2}}{2}}dz\stackrel{symmetry\,of\,the\,Gaussian}{=}\int_{0}^{x-a}e^{-\frac{z^{2}}{2}}dz+\int_{-x-a}^{0}e^{-\frac{z^{2}}{2}}dz \end{align}

And finally, we obtain :

(17)

\begin{align} \mathbb{P}((Z+a)^{2}>x^{2})\geq\mathbb{P}(Z^{2}>x^{2}) \end{align}

• If $x<0$ :

We can write in the last point "$|x|$'' instead of "$x$'' and we get the same conclusion.

• If $a<0$ :

Thanks to the symmetry of the Gaussian and what we desmonstrated, we can write :

(18)

\begin{align} \mathbb{P}((Z+a)^{2}>x^{2})=\mathbb{P}((-Z-a)^{2}>x^{2})=\mathbb{P}((Z+(-a))^{2}>x^{2})\stackrel{-a>0}{\geq}\mathbb{P}(Z^{2}>x^{2}) \end{align}

And we have the final result :

(19)

\begin{align} \boxed{\forall a,x\in\mathbb{R},\,\mathbb{P}((Z+a)^{2}>x^{2})\geq\mathbb{P}(Z^{2}>x^{2})} \end{align}

3.

We have :

(20)

\begin{align} |\hat{m}_{\lambda}| & = & |\{j|(X_{j}^{T}Y)^{2}>\lambda||X_{j}||^{2}\sigma^{2}\}|\\ & = & \underset{j\in\{1,...,p\}}{\sum}\mathbb{I}{}_{\{j|(X_{j}^{T}Y)^{2}>\lambda||X_{j}||^{2}\sigma^{2}\}} \end{align}

so :

(21)

\begin{align} \mathbb{E}[|\hat{m}_{\lambda}|] & = & \underset{j\in\{1,...p\}}{\sum}\mathbb{P}((X_{j}^{T}Y)^{2}>\lambda||X_{j}||^{2}\sigma^{2})\\ & = & \underset{j\in\{1,...p\}}{\sum}\mathbb{P}((X_{j}^{T}\epsilon+X_{j}^{T}f^{*})^{2}>\lambda||X_{j}||^{2}\sigma^{2})\\ & = & \underset{j\in\{1,...p\}}{\sum}\mathbb{P}((\frac{X_{j}^{T}\epsilon}{||X_{j}||\sigma}+\frac{X_{j}^{T}f^{*}}{||X_{j}||\sigma})^{2}>\lambda) \end{align}

where $\frac{X_{j}^{T}\epsilon}{||X_{j}||\sigma}=Z_{j}$ (from A)1)) and where we set $a:=\frac{X_{j}^{T}f^{*}}{||X_{j}||\sigma}$.
According to B)1), the variables $Z_{i}$ are iid $\mathcal{N}(0,1)$, therefore we can apply C)2) and write :

(22)

\begin{align} \mathbb{E}[|\hat{m}_{\lambda}|] & = & \underset{j\in\{1,...p\}}{\sum}\mathbb{P}((Z_{j}+a)^{2}>\lambda)\\ & \geq & \underset{j\in\{1,...p\}}{\sum}\mathbb{P}(Z^{2}>\lambda) \end{align}

And the result :

(23)

\begin{align} \boxed{\mathbb{E}[|\hat{m}_{\lambda}|]\geq p\mathbb{P}(Z^{2}>\lambda) \text{ with } Z\sim\mathcal{N}(0,1)} \end{align}

4.

Assume that $D^{*}\ll p^{1-K}(log(p))^{-\frac{1}{2}}$ (**) .
Let's put $\mathbb{E}$ to work on the result of C)1) (with $\lambda=2Klog(p)$) and because expectation is nondecreasing, we obtain :

(24)

\begin{align} \mathbb{E}[||\hat{f}_{\hat{m}_{2Klog(p)}}-f^{*}||^{2}] & \geq & \mathbb{E}[(|\hat{m}_{2Klog(p)}|-D^{*})2Klog(p)\sigma^{2}] \end{align}

i.e. :

(25)

\begin{align} \boxed{\mathbb{E}[||\hat{f}_{\hat{m}_{2Klog(p)}}-f^{*}||^{2}]\geq2Klog(p)\sigma^{2}(\mathbb{E}[(|\hat{m}_{2Klog(p)}|]-D^{*})} \end{align}

And thanks to C)3) : $\mathbb{E}[(|\hat{m}_{2Klog(p)}|]\geq p\mathbb{P}(Z^{2}>2Klog(p)$), where $\underset{p\rightarrow+\infty}{lim}(2Klog(p))=+\infty$, so,like in B)4), we can write :

(26)

\begin{align} \mathbb{E}[(|\hat{m}_{2Klog(p)}|]\geq p\mathbb{P}(Z^{2}>2Klog(p))\underset{p\rightarrow+\infty}{\sim}p\sqrt{\frac{2}{\pi2Klog(p)}}e^{-\frac{2Klog(p)}{2}}=\frac{p^{1-K}}{\sqrt{\pi Klog(p)}} \end{align}

Let $q(p,K)=p\mathbb{P}(Z^{2}>2Klog(p))$, we have so, by (**) :

(27)

\begin{eqnarray} \mathbb{E}[||\hat{f}_{\hat{m}_{2Klog(p)}}-f^{*}||^{2}] & \geq & 2Klog(p)\sigma^{2}(\mathbb{E}[(|\hat{m}_{2Klog(p)}|]-D^{*})\\ & \geq & 2Klog(p)\sigma^{2}(q(p,K)-D^{*})\\ & & \underset{p\rightarrow+\infty}{\sim}2Klog(p)\sigma^{2}\frac{p^{1-K}}{\sqrt{\pi Klog(p)}}\\ & & \underset{p\rightarrow+\infty}{\sim}p^{1-K}\sigma^{2}\sqrt{\frac{4Klog(p)}{\pi}} \end{eqnarray}

To sum up :

(28)

\begin{align} \boxed{\mathbb{E}[||\hat{f}_{\hat{m}_{2Klog(p)}}-f^{*}||^{2}]\geq something \underset{p\rightarrow+\infty}{\sim}p^{1-K}\sigma^{2}\sqrt{\frac{4Klog(p)}{\pi}}} \end{align}

5.

Assume again $K<1$ and $D^{*}\ll p^{1-K}(log(p))^{-\frac{1}{2}}$.

We can apply bounds (2.21) (page 41) and (2.23) (page 42) : $R[X,D^{*}]$ is of order, when $p$$\rightarrow+\infty$, $D^{*}log(\frac{p}{D^{*}})\sigma^{2}$.

According to C)4) : $\forall f^{*}\in V_{D^{*}}(X),\,\mathbb{E}[||\hat{f}_{\hat{m}_{2Klog(p)}}-f^{*}||^{2}]\geq something \underset{p\rightarrow+\infty}{\sim}p^{1-K}\sigma^{2}\sqrt{\frac{4Klog(p)}{\pi}}$.

In the light of this two remarks, we can conclude that :

(29)

\begin{align} \boxed{For\,K<1\,and\,D^{*}\ll p^{1-K}(log(p))^{-\frac{1}{2}}\,:\,\forall f^{*}\in V_{D^{*}}(X),\,\mathbb{E}[||\hat{f}_{\hat{m}_{2Klog(p)}}-f^{*}||^{2}]\stackrel{p\rightarrow+\infty}{\gg}R[X,D^{*}]} \end{align}