3 6 3 Some Other Minimax Lower Bounds

1) Let $\widehat{\beta}$ be an estimator. Let $\widetilde{\beta} \in \text{argmin}_{\beta \in \mathcal{C}} \, d(\beta, \widehat{\beta})$ be a measurable projection of $\widehat{\beta}$ on $\mathcal{C}$. For any $\beta \in \mathcal{C}$, we can use the triangular inequality :

(1)

\begin{align} d(\beta, \widetilde{\beta}) &\leq d(\beta, \widehat{\beta}) + d(\widetilde{\beta}, \widehat{\beta}) \\ &\leq 2 d(\beta, \widehat{\beta}) \qquad \text{by definition of } \widetilde{\beta} \end{align}

Hence

(2)

\begin{align} \mathbb{E}_{\mathbf{X}\beta} \left[ 2^q d(\beta, \widehat{\beta})^q \right] &\geq \mathbb{E}_{\mathbf{X}\beta} \left[ d(\beta, \widetilde{\beta})^q \right] \\ &\geq \mathbb{E}_{\mathbf{X}\beta} \left[ \mathbf{1}_{\beta \neq \widetilde{\beta}} d(\beta, \widetilde{\beta})^q \right] \\ &\geq \mathbb{E}_{\mathbf{X}\beta} \left[ \mathbf{1}_{\beta \neq \widetilde{\beta}} \min_{\beta \neq \beta' \in \mathcal{C}} d(\beta, \beta')^q \right] \\ &= \mathbb{P}_{\mathbf{X}\beta} \left( \beta \neq \widetilde{\beta} \right) \min_{\beta \neq \beta' \in \mathcal{C}} d(\beta, \beta')^q \end{align}

so that

(3)

\begin{align} \max_{\beta \in \mathcal{C}} \mathbb{E}_{\mathbf{X}\beta} \left[ d(\beta, \widehat{\beta})^q \right] &\geq \frac{1}{2^q} \max_{\beta \in \mathcal{C}} \mathbb{P}_{\mathbf{X}\beta} \left( \beta \neq \widetilde{\beta} \right) \times \min_{\beta \neq \beta' \in \mathcal{C}} d(\beta, \beta')^q \end{align}

The control of the quantity $\max_{\beta \in \mathcal{C}} \mathbb{P}_{\mathbf{X}\beta} \left( \beta \neq \widetilde{\beta} \right)$ is exactly the same as in the proof of lemma 2.4 (where we take $f = \mathbf{X} \beta$ and $\mathcal{V} = \{ \mathbf{X} \beta : \beta\in \mathcal{C} \}$) and ensures

(4)

\begin{align} \max_{\beta \in \mathcal{C}} \mathbb{P}_{\mathbf{X}\beta} \left( \beta \neq \widetilde{\beta} \right) \geq 1 - \left( \frac{2e}{2e+1} \bigvee \max_{\beta \neq \beta' \in \mathcal{C}} \frac{\|\mathbf{X}(\beta - \beta')\|^2}{2 \sigma^2 \log |\mathcal{C}|} \right) \end{align}

This concludes the proof since the right-hand term does not depend on the choice of the estimator $\widehat{\beta}$.

2) With the definition of $\mathcal{C}_r$, one has

(5)

\begin{align} \min_{\beta \neq \beta' \in \mathcal{C}_r} |\beta - \beta'|_q^q &= r^q \min_{\beta \neq \beta' \in \mathcal{C}} |\beta - \beta'|_q^q\\ &= r^q \min_{\beta \neq \beta' \in \mathcal{C}} |\beta - \beta'|_0 \qquad \text{since all coefficients are in } \{0,1\} \\ &\geq r^q D \end{align}

Then, using the definition of $\overline{c}_{\mathbf{X}}$, for all $\beta, \beta' \in \mathcal{C}_r$:

(6)

\begin{align} \| \mathbf{X}(\beta - \beta') \|^2 &\leq \overline{c}_{\mathbf{X}}^2 \| \beta - \beta' \|^2 \\ &= \overline{c}_{\mathbf{X}}^2 r^2 \| \frac{\beta}{r} - \frac{\beta'}{r} \|^2 \\ &= \overline{c}_{\mathbf{X}}^2 r^2 | \frac{\beta}{r} - \frac{\beta'}{r} |_0 \\ &\leq \overline{c}_{\mathbf{X}}^2 r^2 2 D \end{align}

Let's use this inequality together with (2.34):

(7)

\begin{align} \max_{\beta \neq \beta' \in \mathcal{C}_r} \frac{\| \mathbf{X}(\beta - \beta') \|^2}{2 \sigma^2 \log |\mathcal{C}_r|} &\leq \frac{\overline{c}_{\mathbf{X}}^2 r^2 2 D}{2 \sigma^2 \frac{D}{2} \log(\frac{p}{5D})} \\ &= \frac{2 \overline{c}_{\mathbf{X}}^2}{\sigma^2 \log(\frac{p}{5D})} r^2 \\ &= \frac{e}{2e+1} \qquad \text{by definition of } r \end{align}

so that

(8)

\begin{align} 1 - \frac{2e}{2e+1} \bigvee \max_{\beta \neq \beta' \in \mathcal{C}_r} \frac{\| \mathbf{X}(\beta - \beta') \|^2}{2 \sigma^2 \log |\mathcal{C}_r|} &\geq 1 - \frac{2e}{2e+1} \\ &= \frac{1}{2e+1} \end{align}

and finally

(9)

\begin{align} \inf_{\widehat{\beta}} \, \max_{\beta \in \mathcal{C}_r} \mathbb{E}_{\mathbf{X}\beta} \left[ |\beta - \widehat{\beta}|^q_q \right] &\geq \frac{1}{2^q} \frac{1}{2e+1} r^q D \end{align}

which is the expected result.

3) For this question, it is enough to notice that since $\mathcal{C}_r \subset \{\beta : |\beta|_0=D\}$

(10)

\begin{align} \sup_{\beta : |\beta|_0=D} \mathbb{E}_{\mathbf{X}\beta} \left[ |\beta - \widehat{\beta}|^q_q \right] &\geq \max_{\beta \in \mathcal{C}_r} \mathbb{E}_{\mathbf{X}\beta} \left[ |\beta - \widehat{\beta}|^q_q \right] \end{align}

and that by definition of $r$

(11)

\begin{align} \frac{r^q D}{2^q(2e+1)} &= \frac{e^{q/2}}{2^{3q/2} (2e+1)^{1+q/2}} \left( \frac{\sigma}{\overline{c}_{\mathbf{X}}} \right)^q D \left( \log \left( \frac{p}{5D} \right) \right)^{q/2} \end{align}

so that this result is a direct consequence of the previous one.