2 8 5 Goldenshluger Lepski Method

Please share your solution! find instructions on the Help page

---

Let $M$ be a nonzero integer. We write $\mathscr{M}=\{1,...,M \}$
We consider here a collection of models $\{ S_m, \ m\in\mathscr{M} \}$ such that for all $m \leqslant m'$, $S_m \subset S_{m'}$.

For all $m$ in $\mathscr{M}$, we define :

(1)

\begin{align} B(m)=\max_{m'\in\mathscr{M}}\left[ \| \hat{f}_{m'}-\hat{f}_{m'\land m} \|^2 -pen(m')\sigma^2 \right]_+ \end{align}

And we set $\hat{m}=argmin\{B(m)+pen(m)\sigma^2 \ | \ m\in\mathscr{M}\}$

1.

Let $m$ be in $\mathscr{M}$.
Remembering the classical $(x+y)^2 \leqslant 2x^2+2y^2$, we can write :

(2)

\begin{array} {rcl} \| \hat{f}_{\hat{m}}-f^* \|^2 &\leqslant& (\| \hat{f}_{\hat{m}}-\hat{f}_{m} \|+\| \hat{f}_{m}-f^* \|)^2 \\ &\leqslant& 2\| \hat{f}_{\hat{m}}-\hat{f}_{m} \|^2+2\| \hat{f}_{m}-f^* \|^2 \end{array}

If $m\leqslant \hat{m}$,

(3)

\begin{array} {rcl} \| \hat{f}_{\hat{m}}-\hat{f}_{\hat{m}\land m} \|^2 &=&\| \hat{f}_{\hat{m}}-\hat{f}_ m \|^2\\ \| \hat{f}_{m}-\hat{f}_{\hat{m}\land m} \|^2&=&0 \end{array}

If $m > \hat{m}$,

(4)

\begin{array} {rcl} \| \hat{f}_{\hat{m}}-\hat{f}_{\hat{m}\land m} \|^2 &=&0\\ \| \hat{f}_{m}-\hat{f}_{\hat{m}\land m} \|^2&=&\| \hat{f}_{m}-\hat{f}_{\hat{m}} \|^2 \end{array}

Hence :

(5)

\begin{align} \| \hat{f}_{\hat{m}}-f^* \|^2 \leqslant 2\max\left(\| \hat{f}_{\hat{m}}-\hat{f}_{\hat{m}\land m} \|^2 , \| \hat{f}_{m}-\hat{f}_{\hat{m}\land m} \|^2\right) +2\| \hat{f}_{m}-f^* \|^2 \end{align}

Since we have

(6)

\begin{align} \begin{array}{rcl} \max\left(\| \hat{f}_{\hat{m}}-\hat{f}_{\hat{m}\land m} \|^2 , \| \hat{f}_{m}-\hat{f}_{\hat{m}\land m} \|^2\right) &\leqslant& \| \hat{f}_{\hat{m}}-\hat{f}_{\hat{m}\land m} \|^2 + \| \hat{f}_{m}-\hat{f}_{\hat{m}\land m} \|^2 \\ &\leqslant& \| \hat{f}_{\hat{m}}-\hat{f}_{\hat{m}\land m} \|^2 - pen(\hat{m})\sigma^2 \\ && \ \ + \| \hat{f}_{m}-\hat{f}_{\hat{m}\land m} \|^2-pen(m)\sigma^2 \\ && \ \ \ +pen(m)\sigma^2+pen(\hat{m})\sigma^2 \\ &\leqslant& B(m)+B(\hat{m})+pen(m)\sigma^2+pen(\hat{m})\sigma^2 \end{array}, \end{align}

we obtain the following bounds :

(7)

\begin{array} {rcl} \| \hat{f}_{\hat{m}}-f^* \|^2 &\leqslant& 2(B(\hat{m})+pen(\hat{m})\sigma^2+ B(m) + pen(m)\sigma^2) +2\| \hat{f}_{m}-f^* \|^2 \\ &\leqslant& 4( B(m) + pen(m)\sigma^2) +2\| \hat{f}_{m}-f^* \|^2 \end{array}

the last bound coming from the definition of $\hat{m}$.

2.

First of all, we notice that for all $\eta >0$, $\eta(\frac{x^2}{\eta}-2xy+\eta y^2 ) =(x-\eta y)^2 \geqslant 0$.
So, $2xy \leqslant \frac{x^2}{\eta}+\eta y^2$ and eventually :

(8)

\begin{align} \forall x,y \in\mathbb{R}, \forall \eta\in\mathbb{R}_+^*, \ (x+y)^2 \leqslant \frac{\eta+1}{\eta}x^2+(1+\eta)y^2 \end{align}

Now, we can proceed to bound $B(m)$ : for all $m\in\mathscr{M}$, for all $\eta >0$,

(9)

\begin{array} {rcl} B(m)&=& \max_{m'\in\mathscr{M}}\left[ \| Proj_{S_{m'}}(f^*+\epsilon)-Proj_{S_{m'\land m}}(f^*+\epsilon) \|^2 -pen(m')\sigma^2 \right]_+\\ &\leqslant& \max_{m'\in\mathscr{M}}\left[ (\| Proj_{S_{m'}}f^*-Proj_{S_{m'\land m}}f^* \|+\| Proj_{S_{m'}}\epsilon-Proj_{S_{m'\land m}}\epsilon\|)^2 -pen(m')\sigma^2 \right]_+\\ &\leqslant& \max_{m'\in\mathscr{M}}\left[ \frac{\eta+1}{\eta}\| Proj_{S_{m'}}f^*-Proj_{S_{m'\land m}}f^* \|^2+(1+\eta)\| Proj_{S_{m'}}\epsilon-Proj_{S_{m'\land m}}\epsilon\|^2\right. \\ && \ \ \ \ \ \left. -pen(m')\sigma^2 \right]_+ \\ &\leqslant& \max_{m'\in\mathscr{M}} \left[ \frac{\eta+1}{\eta}\| Proj_{S_{m'}}f^*-Proj_{S_{m'\land m}}f^* \|^2 \right]\\ && \ \ \ \ \ + \max_{m'\in\mathscr{M}} \left[ (1+\eta)\| Proj_{S_{m'}}\epsilon-Proj_{S_{m'\land m}}\epsilon\|^2 -pen(m')\sigma^2 \ \right]_+\\ &\leqslant& \max_{m'\geqslant m} \left[ \frac{\eta+1}{\eta}\| Proj_{S_{m'}}f^*-Proj_{S_m}f^* \|^2 \right]\\ && \ \ \ \ \ + \sum_{m'\in\mathscr{M}} \left[ (1+\eta)\| Proj_{S_{m'}}\epsilon-Proj_{S_{m'\land m}}\epsilon\|^2 -pen(m')\sigma^2 \ \right]_+ \end{array}

The last bound coming from the fact that a max of positive terms is bounded by the sum of these terms. We also notice that in this sum, if $m<m'$, the term summed is zero.
Hence, the result :

(10)

\begin{array} {rcl} B(m) &\leqslant& \frac{\eta+1}{\eta} \max_{m'\geqslant m} \left[ \| Proj_{S_{m'}}f^*-Proj_{S_m}f^* \|^2 \right]\\ && \ \ \ \ \ + \sum_{m'\geqslant m} \left[ (1+\eta)\| Proj_{S_{m'}}\epsilon-Proj_{S_m}\epsilon\|^2 -pen(m')\sigma^2 \ \right]_+ \end{array}

For $m\leqslant m'$, we have $S_m \subset S_{m'}$, and $S_{m'}$ is a vectorial subspace, who are known to be convex. Thus, for $m\leqslant m'$,

(11)

\begin{align} \| Proj_{S_{m'}}f^*-Proj_{S_m}f^* \|^2 \leqslant \| f^*-Proj_{S_m}f^* \|^2 \end{align}

The ortogonal projections on linear subspaces have the property of being lipschitz continuous with constant 1. Then, as the operator $(Id-Proj_{S_m})$ is the orthogonal projection onto the orthogonal complement of $S_m$, we can write :

(12)

\begin{align} \| Proj_{S_{m'}}\epsilon-Proj_{S_m}\epsilon\|^2 = \| \left(Id-Proj_{S_m}\right)(Proj_{S_{m'}}\epsilon) \|^2 \leqslant \| Proj_{S_{m'}}\epsilon\|^2 \end{align}

We can gather these in the following bound :

(13)

\begin{align} B(m) \leqslant \frac{\eta+1}{\eta} \| f^*-Proj_{S_m}f^* \|^2 + \sum_{m'\geqslant m} \left[ (1+\eta)\| Proj_{S_{m'}}\epsilon\|^2 -pen(m')\sigma^2 \ \right]_+ \end{align}

Note : From now on, we choose $\eta=\frac{K-1}{2}$ where $K$ is the constant involved in the definition of $pen(m)$. The proof of theorem 2.2 gives us the bound :

(14)

\begin{align} \mathbb{E}\left[ \sum_{m'\geqslant m} \left[ (1+\eta)\| Proj_{S_{m'}}\epsilon\|^2 -pen(m')\sigma^2 \ \right]_+\right] \leqslant \frac{2K(K+1)}{K-1}\sigma^2 \end{align}

3.

We start from the last bound in question 1, and we integrate. We obtain :

(15)

\begin{align} \forall m\in\mathscr{M}, \ \ \mathbb{E}\left[\| \hat{f}_{\hat{m}}-f^* \|^2 \right] \leqslant 4\left( \mathbb{E}\left[ B(m)\right] + pen(m)\sigma^2\right) +2\mathbb{E}\left[\| \hat{f}_{m}-f^* \|^2\right] \end{align}

And, with the same process applied to the last bound of question 2, we have :

(16)

\begin{align} \forall m\in\mathscr{M}, \ \ \mathbb{E}\left[ B(m) \right] ~\leqslant~ \frac{\eta+1}{\eta} \| f^*-Proj_{S_m}f^* \|^2 + \frac{2K(K+1)}{K-1}\sigma^2 \end{align}

As $\epsilon$ is gaussian and centered, we have, for all $m\in\mathscr{M}$, $\mathbb{E}[Proj_{S_m} \epsilon]=0$. Noticing that $f^*$ is a deterministic quantity, we calculate :

(17)

\begin{array} {rcl} \mathbb{E}\left[\| \hat{f}_{m}-f^* \|^2\right]&=&\mathbb{E}\left[\| Proj_{S_m}(f^*+\epsilon)-f^* \|^2\right]\\ &=&\mathbb{E}\left[\| f^*-Proj_{S_m}f^* -Proj_{S_m}\epsilon \|^2 \right] \\ &=& \mathbb{E}\left[\| f^*-Proj_{S_m}f^*\|^2 -2<f^*-Proj_{S_m}f^*,Proj_{S_m}\epsilon> +\|Proj_{S_m}\epsilon\|^2 \right]\\ &=&\mathbb{E}\left[\| f^*-Proj_{S_m}f^*\|^2\right] -2<f^*-Proj_{S_m}f^*,\mathbb{E}\left[Proj_{S_m}\epsilon\right]> \\ &&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ +\mathbb{E}\left[\|Proj_{S_m}\epsilon\|^2 \right]\\ &=&\| f^*-Proj_{S_m}f^*\|^2+\mathbb{E}\left[\|Proj_{S_m}\epsilon\|^2 \right] \end{array}

Lemma A.3 page 214 ensures $\mathbb{E}\left[\|Proj_{S_m}\epsilon\|^2 \right]=d_m\sigma^2$. This implies :

(18)

\begin{align} \mathbb{E}\left[\| \hat{f}_{m}-f^* \|^2\right] = \| f^*-Proj_{S_m}f^*\|^2 + d_m\sigma^2 \end{align}

We can rewrite our bound on $\mathbb{E}[B(m)]$ :

(19)

\begin{align} \forall m\in\mathscr{M}, \ \ \mathbb{E}\left[ B(m) \right] ~\leqslant~ \frac{\eta+1}{\eta} \mathbb{E} \left[ \| \hat{f}_m - f^* \|^2 \right] + \frac{2K(K+1)}{K-1}\sigma^2 \end{align}

Hence, $\forall m\in\mathscr{M}$,

(20)

\begin{array} {rcl} \mathbb{E}\left[\| \hat{f}_{\hat{m}}-f^* \|^2 \right] &\leqslant& 4\left(\frac{K+1}{K-1} \mathbb{E} \left[ \| \hat{f}_m - f^* \|^2 \right] + \frac{2K(K+1)}{K-1}\sigma^2\right) \\ && \ \ \ \ + 4pen(m)\sigma^2 +2\mathbb{E}\left[\| \hat{f}_{m}-f^* \|^2\right] \\ &\leqslant & \left(\frac{4K+4}{K-1}+2\right) \mathbb{E} \left[ \| \hat{f}_m - f^* \|^2 \right] + \frac{8K(K+1)}{K-1}\sigma^2 + 4pen(m)\sigma^2 \\ &\leqslant & \frac{6K+2}{K-1} \mathbb{E} \left[ \| \hat{f}_m - f^* \|^2 \right] + 4pen(m)\sigma^2 + \frac{8K(K+1)}{K-1}\sigma^2 \end{array}

The inequality is valid for all $m$, thus we can write it for the "best" $m$ :

(21)

\begin{align} \mathbb{E}\left[\| \hat{f}_{\hat{m}}-f^* \|^2 \right] \leqslant \inf_{m\in\mathscr{M}} \left\{ \frac{6K+2}{K-1} \mathbb{E} \left[ \| \hat{f}_m - f^* \|^2 \right] + 4pen(m)\sigma^2 \right\} + \frac{8K(K+1)}{K-1}\sigma^2 \end{align}

The bound we obtained is similar to the result of Theorem 2.2.

4.

In this question, we set, for all $m\in\mathscr{M}$, $d_m=m$ and $\pi_m=e^{-m}\frac{e-1}{1-e^{-M}}$.

Firstly, since $\frac{1-e^{-M}}{e-1} \leqslant 1$, we observe that for all $m \in \mathscr{M}$:

(22)

\begin{array} {rcl} pen(m)&=& K\left( \sqrt{d_m}+\sqrt{2log(\frac{1}{\pi_m})} \right)^2\\ &=& K\left( \sqrt{m}+\sqrt{2m +2log(\frac{1-e^{-M}}{e-1})} \right)^2\\ &\leqslant& K\left( \sqrt{m}+\sqrt{2m} \right)^2\\ &\leqslant& K(1+\sqrt2)^2m \end{array}

Then, we had in question 3 :

(23)

\begin{align} \mathbb{E}\left[\| \hat{f}_{m}-f^* \|^2\right] = \| f^*-Proj_{S_m}f^*\|^2 + d_m\sigma^2 \end{align}

We tract from it an useful inequality :

(24)

\begin{align} m\sigma^2 = d_m\sigma^2 \leqslant \mathbb{E}\left[\| \hat{f}_{m}-f^* \|^2\right] \end{align}

Eventually, we proceed to some calculation, building on the result of question 3 :

(25)

\begin{array} {rcl} \mathbb{E}\left[\| \hat{f}_{\hat{m}}-f^* \|^2 \right] &\leqslant& \inf_{m\in\mathscr{M}} \left\{ \frac{6K+2}{K-1} \mathbb{E} \left[ \| \hat{f}_m - f^* \|^2 \right] + 4pen(m)\sigma^2 + \frac{8K(K+1)}{K-1}\sigma^2 \right\}\\ &\leqslant& \inf_{m\in\mathscr{M}} \left\{ \frac{6K+2}{K-1} \mathbb{E} \left[ \| \hat{f}_m - f^* \|^2 \right] + 4K(1+\sqrt{2})^2m\sigma^2 + \frac{8K(K+1)}{K-1}\sigma^2 \right\}\\ &\leqslant& \inf_{m\in\mathscr{M}} \left\{ \frac{6K+2}{K-1} \mathbb{E} \left[ \| \hat{f}_m - f^* \|^2 \right] + \left(4K(1+\sqrt{2})^2 + \frac{8K(K+1)}{K-1}\frac{1}{m}\right)m\sigma^2 \right\}\\ &\leqslant& \inf_{m\in\mathscr{M}} \left\{ \frac{6K+2}{K-1} \mathbb{E} \left[ \| \hat{f}_m - f^* \|^2 \right] \right. \\ && \ \ \ \ \ \ \ \ \ \ \ \ \left. + \left(4K(1+\sqrt{2})^2 + \frac{8K(K+1)}{K-1}\frac{1}{m}\right)\mathbb{E} \left[ \| \hat{f}_m - f^* \|^2 \right] \right\}\\ &\leqslant& \inf_{m\in\mathscr{M}} \left\{ \frac{6K+2}{K-1} \mathbb{E} \left[ \| \hat{f}_m - f^* \|^2 \right] \right. \\ && \ \ \ \ \ \ \ \ \ \ \ \ \left. + \left(4K(1+\sqrt{2})^2 + \frac{8K(K+1)}{K-1}\right)\mathbb{E} \left[ \| \hat{f}_m - f^* \|^2 \right] \right\}\\ &\leqslant& \left(\frac{6K+2}{K-1}+ 4K(1+\sqrt{2})^2 + \frac{8K(K+1)}{K-1}\right) \inf_{m\in\mathscr{M}} \left\{\mathbb{E} \left[ \| \hat{f}_m - f^* \|^2 \right]\right\} \end{array}

Writing $C_K=\left(\frac{6K+2}{K-1}+ 4K(1+\sqrt{2})^2 + \frac{8K(K+1)}{K-1}\right)$, we conclude :

(26)

\begin{align} \mathbb{E}\left[\| \hat{f}_{\hat{m}}-f^* \|^2 \right] \leqslant C_K \inf_{m\in\mathscr{M}} \left\{\mathbb{E} \left[ \| \hat{f}_m - f^* \|^2 \right]\right\} \end{align}

Remark : Removing the positive part in the definition of B(m) does not affect very much the results, as most of the work consists of building inequalities. The negative occurences of B(m) would have been bounded by 0 most of the time.