6 4 3 Risk Bound For Iterative Group Thresholding
$\textbf{A) Proof of Lemma 6.6}$
1) By definition of S',
(1)
\begin{align} |S'| \leqslant |S| + k_{G}^{*} +|\hat \beta_{\bar{m}_{G}^{*}}^{t}|_{0}^{G}. \end{align}
Since for all $J$, $|J| \leqslant c^2\frac{k_{G}^{*}}{q}$, we have $|S|=\sum_{j \in J}\left | Gj \right | = |J|q \leqslant c^2k_{G}^{*}$ , and (6.28) at time $t$ yields $|\hat \beta_{\bar{m}_{G}^{*}}^{t}|_{0}^{G} \leqslant c^2k_{G}^{*}$.
Thus, we get
(2)
\begin{align} |S'| \leqslant (1+2c^2)k_{G}^{*}. \end{align}
2) Using the definition of $b^{t+1}$ and the triangular inequality,
(3)
\begin{align} \left \| \left ( b^{t+1}-\beta^* \right )_S \right \|=\left \| \left ( \Lambda \left ( \hat \beta^t-\beta^* \right ) \right )_S+Z_S \right \|\leqslant \left \| \left ( \Lambda \left ( \hat \beta^t-\beta^* \right ) \right )_S \right \|+\left \| Z_S \right \| \end{align}
By additivity of the square of the euclidean norm, $\left \| Z_S \right \|^2=\sum_{j \in J}\left \| Z_{G_j} \right \|^2$, which yields
(4)
\begin{align} \left \| Z_S \right \| = \sqrt{\sum_{j \in J}\left \| Z_{G_j} \right \|^2} \leqslant \sqrt{|J|\max_{j=1,..,M}\left \| Z_{G_j} \right \|^2} = \sqrt{\frac{|S|}{q}}\max_{j=1,..,M}\left \| Z_{G_j} \right \|=\sqrt{|S|}|Z|_{\infty}^{G}. \end{align}
Furthermore, since $S$ is a subset of $S'$,
(5)
\begin{align} \left \| \left ( \Lambda \left ( \hat \beta^t-\beta^* \right ) \right )_S \right \| \leqslant \left \| \left ( \Lambda \left ( \hat \beta^t-\beta^* \right ) \right )_{S'} \right \|= \left \|\Lambda_{S'S'} \left ( \hat \beta^t-\beta^* \right )_{S'} \right \|. \end{align}
We have seen that $|S'| \leqslant (1+2c^2)k_{G}^{*}$, and $S'$ can be written as an union of $G_j$ (which all have cardinality $q$) over the set $J \cup \left \{ j, \beta^{*}_{G_j} \neq 0 \right \} \cup \left \{ j,(\hat \beta_{\bar{m}_{G}^{*}}^{t})_{G_j} \neq 0 \right \}$ , so we can apply (6.26) to $S'$ which gives
(6)
\begin{align} \left \|\Lambda_{S'S'} \left ( \hat \beta^t-\beta^* \right )_{S'} \right \| \leqslant \delta \left \|\left ( \hat \beta^t-\beta^* \right )_{S'} \right \| \leqslant \delta \left \|\hat \beta^t-\beta^* \right \|. \end{align}
Hence,
(7)
\begin{align} \left \| \left ( b^{t+1}-\beta^* \right )_S \right \| \leqslant \delta \left \|\hat \beta^t-\beta^* \right \|+\sqrt{|S|}|Z|_{\infty}^{G}. \end{align}
$\textbf{B) Proof of Theorem 6.4}$
1) $\hat \beta^0=0$ yields $0=|\hat \beta_{\bar{m}_{G}^{*}}^{0}|_{0}^{G} \leqslant c^2k_G^*$, which is (6.28) at time $0$.
Furthermore, (6.27) and the fact that $\gamma_0=A+B \geqslant A$ ensure that
(8)
\begin{align} \left \| \hat \beta^0 - \beta^* \right \|=\left \| \beta^* \right \| \leqslant \left ( 1+2c \right )A\sqrt{|\beta^*|_{0}^{G}} \leqslant \left ( 1+2c \right )\gamma_0\sqrt{|\beta^*|_{0}^{G}}, \end{align}
which is (6.29) at time $0$.
2) The triangular inequality gives
(9)
\begin{align} \left \| \left ( \hat \beta^{t+1} - \beta^* \right )_{m_{G}^*} \right \| \leqslant \left \| \left ( \hat \beta^{t+1} - b^{t+1} \right )_{m_{G}^*} \right \|+\left \| \left ( b^{t+1} - \beta^* \right )_{m_{G}^*} \right \|. \end{align}
By definition of the hard group thresholding operator,
(10)
\begin{align} \left \|\left (b^{t+1}-H_{\lambda_{t+1}}^{G}\left ( b^{t+1} \right ) \right )_{G_j}\right \|=\left \| b^{t+1}_{G_j}\mathbb{1}_{\left \| b^{t+1}_{G_j} \right \| \leqslant \lambda_{t+1}} \right \| \leqslant \lambda_{t+1}, \end{align}
so
(11)
\begin{align} \left \| \left ( \hat \beta^{t+1} - b^{t+1} \right )_{m_{G}^*} \right \|=\left \| \left ( H_{\lambda_{t+1}}^{G}\left ( b^{t+1} \right ) - b^{t+1} \right )_{m_{G}^*} \right \| \leqslant \sqrt{\frac{k_{G}^{*}}{q}}\lambda_{t+1}=\gamma_{t+1}\sqrt{k_G^{*}}. \end{align}
In addition, since $m_{G}^{*}=\bigcup_{j,\beta^*_{Gj} \neq 0}G_j$ and $|m_{G}^*|=k_{G}^{*} \leqslant c^2k_{G}^{*}$, we can apply Lemma 6.6 to $S=m_{G}^{*}$ to obtain that
(12)
\begin{align} \left \| \left ( b^{t+1} - \beta^* \right )_{m_{G}^*} \right \| \leqslant \delta \left \|\hat \beta^t-\beta^* \right \|+\sqrt{k_G^{*}}|Z|_{\infty}^{G}. \end{align}
Combining these two inequalities yields the desired result :
(13)
\begin{align} \left \| \left ( \hat \beta^{t+1} - \beta^* \right )_{m_{G}^*} \right \| \leqslant \gamma_{t+1}\sqrt{k_G^{*}}+\delta \left \|\hat \beta^t-\beta^* \right \|+\sqrt{k_G^{*}}|Z|_{\infty}^{G}. \end{align}
3) (6.29) at time $t$ gives $\left \|\hat \beta^t-\beta^* \right \| \leqslant \left ( 1+2c \right )\gamma_t \sqrt{k_G^*}$ and (6.27) states that $a \leqslant \frac{c}{\delta \left ( 1+2c \right )}$, so
(14)
\begin{align} \left \| \left ( \hat \beta^{t+1} - \beta^* \right )_{m_{G}^*} \right \| \leqslant \sqrt{k_G^*}\left ( \gamma_{t+1}+ \delta \left ( 1+2c \right )\gamma_t + |Z|_{\infty}^{G} \right ) \leqslant \sqrt{k_G^*}\left ( \gamma_{t+1}+ \delta ca^{-1}\gamma_t + |Z|_{\infty}^{G} \right ). \end{align}
4) Since $S \subset \mathrm{supp}_G\left (\hat \beta_{\bar{m}_{G}^{*}}^{t+1} \right )$, all the coordinates of $\left ( \hat \beta^{t+1} \right )_{S}$ are non zero. But $\hat \beta^{t+1}=H_{\lambda_{t+1}}^{G}\left ( b^{t+1} \right )$, so by definition of the hard group thresholding operator, $\left \| \left ( H_{\lambda_{t+1}}^{G}\left ( b^{t+1} \right ) \right )_{G_j} \right \|\geqslant \lambda_{t+1}$ for every $G_j \subset S$. Hence,
(15)
\begin{align} \gamma_{t+1}\sqrt{|S|}=\lambda_{t+1}\sqrt{\frac{|S|}{q}} \leqslant \left \| \left ( H_{\lambda_{t+1}}^{G}\left ( b^{t+1} \right ) \right )_{S} \right \|. \end{align}
But again, $S \subset \mathrm{supp}_G\left ( \hat \beta_{\bar{m}_{G}^{*}}^{t+1} \right ) \subset \bar{m}_{G}^{*}$, so $\left \| \left ( H_{\lambda_{t+1}}^{G}\left ( b^{t+1} \right ) \right )_{S} \right \|=\left \| \left ( b^{t+1} \right )_{S} \right \|=\left \| \left ( b^{t+1} - \beta^* \right )_{S} \right \|$, and finally Lemma 6.6 gives
(16)
\begin{align} \gamma_{t+1}\sqrt{|S|} \leqslant \delta \left \|\hat \beta^t-\beta^* \right \|+\sqrt{|S|}|Z|_{\infty}^{G}. \end{align}
5) (6.29) at time $t$, (6.27) and the fact that $|S| \leqslant c^2k_G^*$ ensure in turn that
(17)
\begin{align} \delta \left \|\hat \beta^t-\beta^* \right \|+\sqrt{|S|}|Z|_{\infty}^{G} < \delta \left ( 1+2c \right )\gamma_t\sqrt{k_G^*}+c\sqrt{k_G^*}\frac{a-1}{a}B \leqslant c\sqrt{k_G^*}\left (a^{-1}\gamma_t+\frac{a-1}{a}B \right ). \end{align}
And in fact, $\gamma_{t+1}=a^{-\left ( t+1 \right )}A+B=\left ( a^{-t}A+B \right )a^{-1}-Ba^{-1}+B=a^{-1}\gamma_t+\frac{a-1}{a}B$, so by combining (16) and (17) we get $\gamma_{t+1}\sqrt{|S|} < \gamma_{t+1}c\sqrt{k_G^*}$, i.e.
(18)
\begin{equation} |S|<c^2k_G^*. \end{equation}
This means that there is no subset of $\mathrm{supp}_G\left ( \hat \beta_{\bar{m}_{G}^{*}}^{t+1} \right )$ with cardinality $c^2k_G^*$ : this is only possible if $|\hat \beta_{\bar{m}_{G}^{*}}^{t+1}|_{0}^{G}<c^2k_G^*$, which is a stronger version of (6.28) at time $t+1$.
6) The calculations of questions 4) and 5) applied to $S=\mathrm{supp}_G\left ( \hat \beta_{\bar{m}_{G}^{*}}^{t+1} \right )$ directly give
(19)
\begin{align} \left \| \hat \beta^{t+1}_{\bar{m}_{G}^*} \right \|=\left \| \left ( \hat \beta^{t+1} - \beta^* \right )_{\bar{m}_{G}^*} \right \|=\left \| \left ( b^{t+1} - \beta^* \right )_{\bar{m}_{G}^*} \right \| \leqslant \sqrt{k_G^*}\left ( \gamma_t ca^{-1}+c|Z|_{\infty}^{G} \right ) < c\gamma_{t+1}\sqrt{k_G^*}. \end{align}
7) Since $c \geqslant 1$, the result of question 3) alongside the calculations of questions 5) ensures that
(20)
\begin{align} \left \| \left ( \hat \beta^{t+1} - \beta^* \right )_{m_{G}^*} \right \| \leqslant \sqrt{k_G^*}\left ( \gamma_{t+1}+ \delta ca^{-1}\gamma_t + c|Z|_{\infty}^{G} \right ) < (1+c)\gamma_{t+1}\sqrt{k_G^*}. \end{align}
Consequently, the triangular inequality yields
(21)
\begin{align} \left \| \hat \beta^{t+1} - \beta^* \right \| \leqslant \left \| \left ( \hat \beta^{t+1} - \beta^* \right )_{\bar{m}_{G}^*} \right \|+\left \| \left ( \hat \beta^{t+1} - \beta^* \right )_{m_{G}^*} \right \| < (1+2c)\gamma_{t+1}\sqrt{k_G^*}, \end{align}
which is a stronger version of (6.29) at time $t+1$.
$\textbf{C) Proof of Corollary 6.5}$
1) Denoting by $\left \| . \right \|_{F}$ the Frobenius norm and by $X_{G_j,i}$ the $i$-th column of $X_{G_j}$, we have
(22)
\begin{align} \left \| X_{G_j} \right \|_{F}^{2}=\mathrm{Tr}\left ( X_{G_j}^{T}X_{G_j} \right )=\sum_{i=1}^{|G_j|}\left \| X_{G_j,i} \right \|^2=|G_j|, \end{align}
because the columns of X are assumed to be of unit euclidean norm.
2) For any $x,y \in \mathbb{R}^n$, by definition of the operator norm,
(23)
\begin{align} \left \| X_{G_j}^{T}x-X_{G_j}^{T}y \right \|=\left \| X_{G_j}^{T}\left ( x-y \right ) \right \|\leqslant \left \| X_{G_j}^{T} \right \|_{op}\left \| x-y \right \|. \end{align}
Since $\left \| X_{G_j}^{T} \right \|_{op}=\left \| X_{G_j} \right \|_{op}$, we have proved that $F : x \mapsto \left \| X_{G_j}^{T}x \right \|$ is $\left \| X_{G_j} \right \|_{op}$-Lipschitz.
3) Since $X_{G_j}^{T} \varepsilon=Z_{G_j}$, applying the Gaussian Concentration Inequality to $\varepsilon$ and $F$ yields
(24)
\begin{align} \mathrm{P}\left [ \left \| Z_{Gj} \right \| \geqslant \mathrm{E}\left [ \left \| Z_{G_j} \right \| \right ]+\sigma\left \| X_{G_j} \right \|_{op}\sqrt{2u}\right ] \leqslant e^{-u}. \end{align}
Furthermore, the Jensen inequality ensures that $\mathrm{E}\left [ \left \| Z_{G_j} \right \| \right ]^2 \leqslant \mathrm{E}\left [ \left \| X_{G_j}^T\varepsilon \right \|^2 \right ]=\left \| \mathrm{E}\left [ X_{G_j}^T\varepsilon \right ] \right \|^2+\mathrm{Tr}\left ( X_{G_j}^T\sigma^2I_nX_{G_j} \right ) =\sigma^2\left \| X_{G_j} \right \|_F^2=\sigma^2|G_j|$,
so
(25)
\begin{align} \mathrm{E}\left [ \left \| Z_{G_j} \right \| \right ] \leqslant \sigma\sqrt{|G_j|}. \end{align}
Hence,
(26)
\begin{align} \mathrm{P}\left [ \left \| Z_{Gj} \right \| \geqslant \sigma\left ( \sqrt{|G_j|}+\left \| X_{G_j} \right \|_{op}\sqrt{2u} \right )\right ] \leqslant \mathrm{P}\left [ \left \| Z_{Gj} \right \| \geqslant \mathrm{E}\left [ \left \| Z_{G_j} \right \| \right ]+\sigma\left \| X_{G_j} \right \|_{op}\sqrt{2u}\right ] \leqslant e^{-u}. \end{align}
4) With an union bound, we get
(27)
\begin{align} \mathrm{P}\left [ \left | Z \right |_{\infty}^G \geqslant \sigma\left ( 1+\phi_G\sqrt{2\log M + 2L} \right )\right ] &\leqslant \sum_{j=1}^{M}\mathrm{P}\left [ \frac{\left \| Z_{Gj} \right \|}{\sqrt{|G_j|}} \geqslant \sigma\left ( 1+\phi_G\sqrt{2\log M +2L} \right )\right ] \\ &\leqslant \sum_{j=1}^{M}\mathrm{P}\left [ \left \| Z_{Gj} \right \| \geqslant \sigma\left ( \sqrt{|G_j|}+\left \| X_{G_j} \right \|_{op}\sqrt{2\log M +2L} \right )\right ] \\ &\leqslant Me^{-\log M-L} \\ &=e^{-L}. \end{align}
$B$ has been defined in such a way as to have $\left \{ \left | Z \right |_{\infty}^G \geqslant \sigma\left ( 1+\phi_G\sqrt{2\log M + 2L} \right ) \right \} =\left \{ B \leqslant \frac{a}{a-1}\left | Z \right |_{\infty}^G \right \}$, so we have proved that
(28)
\begin{align} \mathrm{P}\left [ B \leqslant \frac{a}{a-1}\left | Z \right |_{\infty}^G \right ] \leqslant e^{-L}. \end{align}
In addition, $A$ has exactly the same definition here as in Theorem 6.3, so the proof of said theorem directly yields $\mathrm{P}\left [ A < \frac{\left \| \beta^* \right \|}{\left ( 1+2c \right )\sqrt{k_G^*}} \right ] \leqslant \mathrm{P}\left [ A < \frac{\left \| \beta^* \right \|}{\left ( 1+2c \right )} \right ] \leqslant e^{-L}$.
Consequently,
(29)
\begin{align} \mathrm{P}\left [ B > \frac{a}{a-1}\left | Z \right |_{\infty}^G \cap A \geqslant \frac{\left \| \beta^* \right \|}{\left ( 1+2c \right )\sqrt{k_G^*}} \right ] \geqslant 1-e^{-2L}. \end{align}
