$\newcommand{\prodscal}[2]{\left\langle#1,#2\right\rangle}$
$\newcommand\btht{ \hat\beta_\lambda}$
$\newcommand\eps{\Large{\varepsilon}\normalsize}$
$\newcommand\sp{\hspace{1cm}}$
$\newcommand\lsp{\hspace{0.5cm}}$
$\newcommand\llsp{\hspace{0.2cm}}$
$\newcommand\Rp{\mathbb{R}^p}$
$\newcommand\Rn{\mathbb{R}^n}$
$\newcommand\zro{\Large 0 \normalsize}$
A) Deterministic Bound
1.
We write here $\mathcal{L}(\beta)=\|Y-X\beta\|^2+\lambda\sum\limits_{\substack{k=1}}^{M}{\|\beta_{Gk}\|}$ the Group Lasso function, taking an unique coefficient $\lambda>0$ for every $k\in\lbrace1,...,M\rbrace$.
Applying formula p.88 for Group Lasso subdifferential, for any $\beta\in \mathbb{R}^p$, we have
(1)As the Group Lasso estimator $\hat\beta_\lambda$ minimizes $\mathcal{L}(\beta)$, which is convex, we have thanks to (4.2) : $0\in\partial\mathcal{L}(\hat\beta_\lambda)$
Using (1), there exists $\hat z\in\partial\sum\limits_{\substack{k=1}}^{M}{\|\hat\beta_{\substack\lambda{Gk}}\|}$ such that we obtain the equality $-2X^T(Y-X\hat\beta)+\lambda \hat z =0$
As $Y=X\beta^*+\eps$ we can replace in last expression and obtain
Now, Let $\beta\in \mathbb{R}^p$, by applying scalar product with $\btht-\beta$ to (2) we get
$\sp 2\prodscal{X^T(X\btht-X\beta^*)}{\btht-\beta}-2\prodscal{X^T \eps}{\btht-\beta}+ \lambda \prodscal{\hat z}{\btht-\beta}=0$
$\Leftrightarrow \sp 2\prodscal{X(\btht-X\beta^*)}{X(\btht-\beta)}-2\prodscal{X^T \eps}{\btht-\beta}+ \lambda \prodscal{\hat z}{\btht-\beta}=0$
Since our full norm $\|\|_{\lbrace1,...,M\rbrace}$ is convex, its subgradient is monoton and we have $\prodscal{\hat z}{\btht-\beta} \geqslant \prodscal{ z}{\btht-\beta}$ for all $z\in\partial\sum\limits_{\substack{k=1}}^{M}{\|\beta_{Gk}\|}$
Thus,
(3)2.
$\newcommand\bbk{(\hat\beta_\lambda -\beta)_{Gk}}$
$\newcommand\Kb{\cal{K}(\beta)}$
As $\partial\sum\limits_{\substack{k=1}}^{M}{\|\beta_{Gk}\|} = \lbrace z\in \Rp : z_{Gk}= \beta_{Gk} / \|\beta_{Gk}\| \lsp if \lsp \| \beta_{Gk}\| >0, \lsp \|z_{Gk}\| \le 1 \lsp else \rbrace$.
Let's take $z\in\partial\sum\limits_{\substack{k=1}}^{M}{\|\beta_{Gk}\|}$ such that :
For $k \in \Kb$ we have $z_{Gk}= \beta_{Gk} / \|\beta_{Gk}\| \lsp \Rightarrow \|z_{Gk}\|=1 \lsp \Rightarrow | \prodscal{z_{Gk}}{\bbk} | \le \| \bbk \|$
$\Rightarrow \prodscal{z_{Gk}}{\bbk} \llsp\ge \llsp -\| \bbk \|$
For $k \notin \Kb, \lsp \beta_{Gk} = 0$,
$\sp \sp$if $\bbk = 0$ then $\prodscal{z_{Gk}}{\bbk} = \| \bbk \| = 0$
$\sp \sp$if $\bbk \ne0$ we set $z_{Gk} = \displaystyle\frac{\bbk}{\|\bbk\|} \lsp \Rightarrow \prodscal{z_{Gk}}{\bbk} = \| \bbk \|$
Hence,
$\prodscal{z}{\btht - \beta} = \sum\limits_{\substack{k\in \Kb}}{\prodscal{z_{Gk}}{\bbk}} \lsp + \lsp \sum\limits_{\substack{k\notin \Kb}}{\prodscal{z_{Gk}}{\bbk}}$
$= \sum\limits_{\substack{k\in \Kb}}{\prodscal{z_{Gk}}{\bbk}} \lsp + \lsp \sum\limits_{\substack{k\notin \Kb}}{\|\bbk \|}$
$\ge -\sum\limits_{\substack{k\in \Kb}}{\|\bbk \|} \lsp + \lsp \| \btht - \beta \|_{\Kb^c}$
By multiplying inequality by $-\lambda$ we obtain the result :
(4)3. Let $\lambda \ge 3 max_{k=1,...,M} \| X_{Gk}^T \eps \|$
Then we have, $2\prodscal{X^T \eps}{\btht-\beta} = 2 \sum\limits_{\substack{k=1}}^{M}{ \prodscal{X_{Gk}^T \eps}{\bbk} }$
$\le \lsp 2 \sum\limits_{\substack{k=1}}^{M}{ \| X_{Gk}^T \eps \| \|\bbk \| } \lsp \le \lsp 2 \llsp max_{k=1,...,M}( \| X_{Gk}^T \eps \| ) \sum\limits_{\substack{k=1}}^{M}{ \| \bbk \| }$
$\le \lsp \displaystyle\frac{2 \lambda }{3} \llsp \sum\limits_{\substack{k=1}}^{M}{\| \bbk \| } \lsp \le \lsp \displaystyle\frac{2 \lambda }{3} \llsp ( \llsp \| \btht - \beta \|_{\Kb} + \| \btht - \beta \|_{\Kb^c} \llsp )$
Thus, we have $\lsp 2\prodscal{X^T \eps}{\btht-\beta}\lsp \le \lsp \displaystyle\frac{2 \lambda }{3} \llsp ( \llsp \| \btht - \beta \|_{\Kb} + \| \btht - \beta \|_{\Kb^c} \llsp )$
Using this inequality with (4) in (3) we obtain :
(5)$\newcommand\beb{ \| X(\beta^* - \beta)\| }$
$\newcommand\ble{ \| X(\btht - \beta^*)\| }$
$\newcommand\blb{ \| X(\btht - \beta)\| }$
$\newcommand\Kg{K_G(\beta)}$
4. By using Al Kashi formula for triangle $(\beta , \btht , \beta^*)$ we obtain :
$\ble^2 + \blb^2 \llsp = \llsp \beb^2 + 2\prodscal{X(\btht-\beta^*)}{X(\btht-\beta)}$
So, if $2\prodscal{X(\btht-\beta^*)}{X(\btht-\beta)} \llsp \le \llsp 0$ we have directly the result because $\ble^2 + \blb^2 \llsp \le \llsp \beb^2$
Else, using inequality (5) we get $\ble^2 + \blb^2 \llsp \le \llsp \beb^2 + \displaystyle\frac{\lambda}{3} (5 \| \btht - \beta \|_{\Kb} - \| \btht - \beta \|_{\Kb^c} )$
$\le \llsp \beb^2 + 2\lambda \| \btht - \beta \|_{\Kb}$
Then, regarding definition (4.18) of $\Kg$ we have $\btht - \beta \in \mathcal{C}_G(\beta)$ and thus,
$\Kg \le \llsp \displaystyle\frac{ \sqrt{|card\Kb |} \llsp \blb}{\| \btht - \beta \|_{\Kb}} \llsp$for $\beta \ne 0$, otherwise $card\Kb$=0 $\Rightarrow \| \btht - \beta \|_{\Kb} = 0$
by combining this with previous inequality
$\ble^2 + \blb^2 \llsp \le \llsp \beb^2 +\displaystyle\frac{ 2\lambda \sqrt{|card\Kb |} \llsp \blb}{\Kg}$
Finally, in this inequality, we use $(a-b)^2 \ge 0 \llsp \Leftrightarrow \llsp 2ab - b^2 \le a^2$ to obtain
$\ble^2 \llsp \le \llsp \beb^2 + \displaystyle\frac{\lambda^2 card\Kb }{\Kg^2}$
As it is true for any $\beta \in \Rp \backslash \lbrace 0 \rbrace$ we have (4.25)
$\sp \sp \ble^2 \llsp \le \llsp \underset{\beta \in \Rp \backslash \lbrace 0 \rbrace}{\text{inf}}\llsp \LARGE\lbrace \normalsize\beb^2 + \displaystyle\frac{ \lambda^2 card\Kb }{\Kg^2} \LARGE\rbrace$
B) Stochastic control
$\newcommand\Xg{X_{Gk}^T}$
1. Let $k\in\lbrace1,...,M\rbrace$. We set $z\in\Rn, \llsp F(z)= \displaystyle\frac{ \|\Xg z\|}{|\Xg|_{op}}$.
and we will prove F is 1-lipschitz. Let $z_1,z_2\in \Rn$
$|F(z_1)-F(z_2)| \llsp = \llsp \displaystyle\frac{|\Xg (z_1-z_2) |}{|\Xg|_{op}} \displaystyle\frac{ \|z_1-z_2\|}{ \|z_1-z_2\|} \llsp = \llsp \huge | \normalsize \Xg \displaystyle\frac{z_1-z_2}{ \|z_1-z_2\|} \huge | \normalsize \llsp \displaystyle\frac{\|z_1-z_2\|}{|\Xg|_{op}}$
As $\huge \|\normalsize \displaystyle\frac{z_1-z_2}{ \|z_1-z_2\|} \huge \| \normalsize\llsp = \llsp 1$, we can write a bound with operator norm: $\huge | \normalsize \Xg \displaystyle\frac{z_1-z_2}{ \|z_1-z_2\|} \huge | \normalsize \le |\Xg|_{op}$
Then $|F(z_1)-F(z_2)| \llsp \le \llsp \|z_1-z_2\|$, so F is 1-Lipschitz.
Consequently, as $\eps \sim \cal{N}(\zro,\sigma^2 I_{p/M} )$, we can use gaussian concentration inequality on $F(\eps)$. There exists some $\xi_k \sim \eps(1)$ such that :
$\displaystyle\frac{\| \Xg \eps\|}{|\Xg|_{op}} \llsp \le \llsp \displaystyle\frac{E[ \| \Xg \eps\|]}{|\Xg|_{op}} + \sigma \sqrt{2\xi_k}$
Plus, we get from Jensen inequality and exercise 1.6.5 that $E[ \| \Xg \eps\|]\le \sqrt{E[ \| \Xg \eps\|^2]} = \sqrt{\sigma^2 Tr(X_{Gk} \Xg )} = \sigma \| \Xg\|_F$
Which leads us to the result, for each $k = 1,...,M$ there exists a $\xi_k \sim \eps(1)$ such that :
2. Let $k\in\lbrace1,...,M\rbrace$, we have $T=card(G_k)=p/M$ and $\|X_{Gk}\|_F^2=Tr(\Xg X_{Gk}) = \sum\limits_{\substack{i=1}}^{T}{(\Xg X_{Gk})_{i,i}}$
Besides, for each $i\in\lbrace1,...,T\rbrace,\llsp (\Xg X_{Gk})_{i,i} = \sum\limits_{\substack{i=1}}^{T}{(X_{Gk})_{j,i}^2}=1$, as every column's norm is 1 by hypothesis. Thus, $\|X_{Gk}\|_F^2=T$.
Using this in inequality (6) we get that for any $k\in\lbrace1,...,M\rbrace$ there exists a $\xi_k \sim \eps(1)$ such that :
$\| \Xg \eps\| \llsp \le \llsp \sigma \sqrt{T}+ |\Xg|_{op}\sigma \sqrt{2\xi_k}$
which means there exists a set of exponential variables $S= (\xi_k)_{k=1,...,M}$ such that :
$\underset{k=1,...,M}{max}\|\Xg \eps\| \llsp\le\llsp \sigma\sqrt{T} + \underset{k=1,...,M}{max}[|\Xg|_{op}]\llsp \sigma\sqrt{2\llsp\underset{k=1,...,M}{max}\xi_k}$
We use exponential law repartition function to write that for $k\in\lbrace1,...,M\rbrace,\llsp L>0$
$P(\xi_k > L + log(M))=e^{-L-log(M)}=\displaystyle\frac{e^{-L}}{M}$.
Then,
So we get (4.26) with probability superior to $1-e^{-L}$.
3. We set $\lambda = 3\sigma(\sqrt{T} + \Phi_G \sqrt{2L+2log(M)})$. This way, according to (4.26), we have $\lambda \ge 3 \underset{k=1,...,M}{max}\|\Xg \eps\|$ with probability at least $1-e^{-L} \Rightarrow$ We have with probability $1-e^{-L}$ :
$\|X(\btht-\beta^*)\|^2 \llsp\le\llsp \underset{\beta\ne\zro}{inf}\lbrace \|X(\beta-\beta^*)\|^2 + \displaystyle\frac{|\Kb|}{\Kg} 9\sigma^2 (\sqrt{T} + \Phi_G \sqrt{2L+2log(M)}\llsp)^2 \rbrace$
Then we use that $(a-b)^2 \ge \zro \llsp\Leftrightarrow\llsp a^2 -2ab+b^2 \ge \zro\llsp\Leftrightarrow\llsp 2a^2+2b^2\ge (a+b)^2$ with $a=\sqrt{T} \llsp and \llsp b=\Phi_G (\sqrt{2L+2log(M)}\llsp)$.
In conclusion, With all above mentionned hypothesis, we obtain the following inequality with probability at least $1-e^{-L}$
(9)Which is the risk bound (4.20).
C) Block descent algorithm
$\newcommand\nxa{\|x_\alpha\|}$
$\newcommand\Ca{(A^TA+\alpha I)}$
$\newcommand\aty{A^TY}$
$\newcommand\naty{\|A^TY\|}$
$\newcommand\Asvd{\sum\limits_{\substack{j=1}}^{r}{\sigma_j u_j v_j^T}}$
$\newcommand\ATsvd{\sum\limits_{\substack{j=1}}^{r}{\sigma_j v_j u_j^T}}$
$\newcommand\divi{\displaystyle\frac{\alpha}{\sigma_k^2 + \alpha}}$
$\newcommand\divis{\displaystyle\frac{\sigma_k}{\sigma_k^2 + \alpha}}$
$\newcommand\atyv{\prodscal{\aty}{v_k}}$
Let's set $Y \in \mathbb{R}^n , \sp A\in \mathcal{M}^{n,p}(\mathbb{R}), \sp \lambda>0$
and $\sp \alpha\nxa=\lambda/2 \sp where \sp x_\alpha=\Ca^{-1}\aty$
1. Singular values decomposition of A is
$A=\Asvd \sp$ where
$\sp - r= rank(A)$
$\sp - (u_1,...,u_r)$ is an orthonormal basis in $\mathbb{R}^n$
$\sp - (v_1,...,v_r)$ is an orthonormal basis in $\mathbb{R}^p$
and we have for $j\in{1,...,r}$ :
(10)Then, $\aty = (\Asvd)^T Y = \sum\limits_{\substack{j=1}}^{r}{\sigma_j v_j u_j^T Y} = \sum\limits_{\substack{j=1}}^{r}{\sigma_j u_j^T Y v_j }$ where $\sigma_j u_j^T Y$ is a scalar.
Thus, $\aty \in \mathbb{R}^p$ is a linear combination of the orthonormal basis $(v_1,...,v_r) \Rightarrow \aty \in span(v_1,...,v_r)$.
2. Thanks to last question's decomposition,
$\sum\limits_{\substack{k=1}}^{r}{ \divi \atyv .v_k } = \sum\limits_{\substack{k=1}}^{r}{ \divi \sigma_k u_k^T Y .v_k} = \alpha (\sum\limits_{\substack{k=1}}^{r}{ \divis v_k u_k^T}) Y \\$
Calling $C= \sum\limits_{\substack{k=1}}^{r}{ \divis v_k u_k^T}$, let's show that
$C = \Ca^{-1}A^T \sp \Leftrightarrow \sp \Ca C=A^T$
Indeed, $\Ca C$
$= \sum\limits_{\substack{k=1}}^{r}{ \divis \Ca v_k u_k^T}$
$= \sum\limits_{\substack{k=1}}^{r}{ \divis (A^TA v_k + \alpha I_p v_k ) u_k^T}$
$= \sum\limits_{\substack{k=1}}^{r}{ \divis (\sigma_k^2 + \alpha) v_k u_k^T}$ with $(9)$
Finally, $\Ca C = A^T$ and so on
$\newcommand\phia{\varphi(\alpha)}$
3. Let's call $\varphi : \alpha \rightarrow \alpha^2 \nxa^2 = \sum\limits_{\substack{k=1}}^{r}{ \divi \atyv^2}$
We notice indeed that :
- $\lim\limits_{\substack{\alpha \rightarrow 0}}{\phia} = 0$
- $\lim\limits_{\substack{\alpha \rightarrow +\infty}}{\phia} = \sum\limits_{\substack{k=1}}^{r}{ \left[ \atyv^2 \lim\limits_{\substack{\alpha \rightarrow +\infty}}{\divi} \right]}= \sum\limits_{\substack{k=1}}^{r}{ \atyv^2} = \naty^2$
Besides, $\displaystyle\frac{\partial \phia}{\partial \alpha} = 2\alpha \nxa^2 + \alpha^2 \displaystyle\frac{\partial \nxa^2}{\partial \alpha}$
$= 2\alpha \nxa^2 + \alpha^2 \sum\limits_{\substack{k=1}}^{r}{ \displaystyle\frac{-2}{(\sigma_k^2 + \alpha)^3} \atyv^2 }$
$= 2 \sum\limits_{\substack{k=1}}^{r}{ \displaystyle\frac{\alpha \sigma_k^2}{(\sigma_k^2 + \alpha)^3} \atyv^2 } \ge 0$
We conclude that $\varphi$ is non decreasing from $\mathbb{R^{+*}}$ on $\Large \textbf{]}\normalsize 0, \naty^2 \Large \textbf{[}$.
4. As $\lambda > 0$, a solution exists to the problem $\alpha \nxa = \lambda / 2$ with $\alpha >0$
$\Leftrightarrow \sp \exists \alpha > 0 \sp / \sp \phia = (\lambda/2)^2$
$\Leftrightarrow \sp \exists \alpha > 0 \sp / \sp (\lambda/2)^2 < \naty ^2$ by applying intermediates values theorem to $\varphi$ (which is continuous) on $\mathbb{R^{+*}}$ with values on $\Large \textbf{]}\normalsize 0, \naty^2 \Large \textbf{[}$.