2 8 2 Risk Bounds For The Different Sparsity Settings

Let us investigate the different risk bounds we can obtain according to various sparsity settings in the linear regression model (2.2).

A) Coordinate-sparse setting:

In that case, a model $m\in\mathscr{M}$ corresponds to an element of $\mathscr{M}=\mathscr{P}(\{1,...,p\})$, i.e a set of active coordinates among the $p$ available. We use the weights defined by: $\pi_{m}={p\choose |m|}^{-1}e^{-|m|}(e-1)/(e-e^{-p})$. For all $\beta\in\mathbb R^{p}$ we denote $supp(\beta)=\{j:\beta_{j}\neq0\}$ and $|\beta|_{0}=|supp(\beta)|$.

1. For $m\in\mathscr{M}$, using the Pythagorean formula and Lemma A.3 we have:

(1)

\begin{align} \mathbb E[||\widehat{f}_{m}-f^{\ast}||^2]=\mathbb E[||(I-Proj_{S_{m}})X\beta^{\ast}||^2+||Proj_{S_{m}}\varepsilon||^2]=||(I- Proj_{S_{m}})X\beta^{\ast}||^2+d_{m}\sigma^2 \end{align}

For the first term, by definition of the projection onto the subspace $S_{m}$, and noticing that $S_{m}=Span\{X_{j}:j\in m\}$ can also be described as $S_{m}=\{X\beta:supp(\beta)=m\}$, we can write that:

(2)

\begin{align} ||(I-Proj_{S_{m}})X\beta^{\ast}||^2=\inf_{W\in S_{m}}\{||X\beta^{\ast}-W||^2\}=\inf_{\beta:supp(\beta)=m}\{||X\beta^{\ast}-X\beta||^2\} \end{align}

And for the second term, assuming that $X$ is invertible, we have that $d_{m}=\dim(S_{m})=card(m)=|\beta|_{0}$ for all $\beta$ such as $supp(\beta)=m$.

We thus finally have that:

(3)

\begin{align} \mathbb E[||\widehat{f}_{m}-f^{\ast}||^2]=\inf_{\beta:supp(\beta)=m}\{||X\beta^{\ast}-X\beta||^2+|\beta|_{0}\sigma^2\} \end{align}

2. Let us focus on the risk associated to the estimator $\widehat{f}=X\widehat{\beta}$ defined by (2.9). Theorem 2.2 provides a constant $C''_{K}>1$ depending only on $K>1$ such that:

(4)

\begin{align} \mathbb E[||X\widehat{\beta}-X\beta^{\ast}||^2]\leq C''_{K}\min_{m\in\mathscr{M}\setminus\emptyset}\{\mathbb E[||\widehat{f}_{m}-f^{\ast}||^2]+\sigma^2(1+\log(\frac{1}{\pi_{m}}))\} \end{align}

Plugging the result of A)1. and also using the Lemma 2.1, we obtain:

(5)

\begin{align} &\mathbb E[||X\widehat{\beta}-X\beta^{\ast}||^2]\\ &\leq C''_{K}\min_{m\in\mathscr{M}\setminus\emptyset}\inf_{\beta:supp(\beta)=m}\{||X\beta^{\ast}-X\beta||^2+\sigma^2|\beta|_{0}(3+\log(\frac{p}{|\beta|_{0}}))\\ &+\sigma^2+\log\left(\frac{e}{e-1}\right)\sigma^2\} \end{align}

As we compute our upper-bound on $\mathscr{M}\setminus\emptyset$, we have that $|\beta|_{0}\geq 1$. This allows us to establish the first expected inequality:

(6)

\begin{align} \mathbb E[||X\widehat{\beta}-X\beta^{\ast}||^2]\leq C_{K}\min_{m\in\mathscr{M}\setminus\emptyset}\inf_{\beta:supp(\beta)=m}\{||X\beta^{\ast}-X\beta||^2+\sigma^2|\beta|_{0}(1+\log(\frac{p}{|\beta|_{0}})\} \end{align}

To state the second inequality, we just need to see that going through all the $\beta$ of the model $m$ for every $m\in\mathscr{M}\setminus\emptyset$ is exaclty the same as checking all the $\beta$ of $\mathbb R^{p}-\{0\}$.
Hence, this gives that:

(7)

\begin{align} \mathbb E[||X\widehat{\beta}-X\beta^{\ast}||^2]\leq C_{K}\inf_{\beta\in\mathbb R^{p}\setminus\{0\}}\{||X\beta^{\ast}-X\beta||^2+\sigma^2|\beta|_{0}(1+\log(\frac{p}{|\beta|_{0}})\} \end{align}

B) Group-sparse setting:

We split now our coordinates into $M$ groups of $p/M$ variables, so that in this section, a model $m\in\mathscr{M}$ corresponds to an element of $\mathscr{M}=\mathscr{P}(\{1,...,M\})$, i.e a set of active groups among the $M$ available. The associated weights are $\pi_{m}={M\choose |m|}^{-1}e^{-|m|}(e-1)/(e-e^{-M})$, and we define for a given vector its number of active groups $\mathscr{K}(\beta)=\{k:\beta_{G_{k}}\neq0\}$.

1. We need to adapt to the new objects: here, for a given model $m$, the total number active coordinates of one of its elements, is its number of active groups times the number of actives coordinates per group:

(8)

\begin{align} \forall m \in \mathscr{M}, \forall \beta_{0}:\mathscr{K}(\beta_{0})=m, |\beta_{0}|_{0}=\frac{|\mathscr{K}(\beta_{0})|p}{M} \end{align}

Then, using the same agruments involved in A)1, we have that:

(9)

\begin{align} \mathbb E[||\widehat{f}_{m}-f^{\ast}||^2]=\inf_{\beta:\mathscr{K}(\beta)=m}\{||X\beta^{\ast}-X\beta||^2+\frac{|\mathscr{K}(\beta)|p}{M}\sigma^2\} \end{align}

2. The method is exactly the same as for A)2. We apply the Theorem 2.2, apply the inequality on the weights, use the same technic of splitting the infimum and the fact that we are in $\mathscr{M}\setminus\emptyset$, so that we can find a constant $C_{K}>1$ depending only on $K>1$ satisfying:

(10)

\begin{align} \mathbb E[||X\widehat{\beta}-X\beta^{\ast}||^2]\leq C_{K}\min_{m\in\mathscr{M}\setminus\emptyset}\{\mathbb E[||\widehat{f}_{m}-f^{\ast}||^2]+|m|\sigma^2(1+\log(\frac{M}{|m|}))\} \end{align}

We then insert the result of B)1. into it so that we have the following inequality:

(11)

\begin{align} \mathbb E[||X\widehat{\beta}-X\beta^{\ast}||^2]\leq C_{K}\inf_{\beta\in\mathbb R^{p}\setminus\{0\}}\{||X\beta^{\ast}-X\beta||^2+|\mathscr{K}(\beta)|\sigma^2(1+\frac{p}{M}+\log(\frac{M}{|\mathscr{K}(\beta)|})\} \end{align}

3. With (9) we notice that the extra-term in the bound can be written this way:

(12)

\begin{align} |\mathscr{K}(\beta)|(1+\frac{p}{M}+\log(\frac{M}{|\mathscr{K}(\beta)|}))=|\beta|_{0}+\frac{M}{p}|\beta|_{0}(1+\log(\frac{p}{|\beta|_{0}})) \end{align}

This last equality shows us that the ratios of the bound in Coordinate-Sparsity on the bound in Group-Sparsity roughly behaves like $\frac{p}{M}$, so that if our problem is such as $M<<p$, the bound on Coordinate-Sparsity would be potentially very important compared to the Group-Sparsity one. Using then a Group-Sparsity setting in that case would give us more severe and accurate selection On the contrary, if $M$ gets approches $p$ this means that we would get closer to a system where groups can hardly be defined, so that we should focus on Coordinate Sparsity to avoid a cost in precision.

C) Sparse group-sparse setting:

In this last part, we combine the two aspects considered early on: let us consider a model $m$ of $\mathscr{M}$ as being a set of groups, and a family of active coordinates for each one of these selected groups, ie $m=(g,\{J_{k}\}_{k \in g})$. Here, we consider the following weights: $\pi_{m}=\frac{1}{Z}\frac{e^{-|g|}}{M\choose |g|}\prod_{k\in g} \frac{e^{-|J_{k}|}}{|G_{k}| \choose |J_{k}|}$ with $Z=\frac{\alpha-\alpha^{M+1}}{1-\alpha}$ and $\alpha=\frac{1-e^{-p/M}}{e(e-1)}$. We finally define $\mathscr{J}_{k}(\beta)=\{j \in G_{k}:\beta_{j} \neq 0\}$.

1. To get the total number of active coordinates here, we need to sum the number of active coordinates of all the active groups, ie $\sum_{k\in g} |\mathscr{J}_{k}(\beta)|$. Then, with the same arguments used in A)1. and B)1, we find that:

(13)

\begin{align} \mathbb E[||\widehat{f}_{(g,\{J_{k}\}_{k \in g})}-f^{\ast}||^2]=\inf_{\beta:\mathscr{K}(\beta)=g,\mathscr{J}_{k}(\beta)=J_{k}}\{||X\beta^{\ast}-X\beta||^2+\sum_{k\in g} |\mathscr{J}_{k}(\beta)|\sigma^2\} \end{align}

2. Again, we can show with the method of A)2. and B)2. that we can find some $C_{K}>1$ depending only on $K>1$ satisfying:

(14)

\begin{align} &\mathbb E[||X\widehat{\beta}-X\beta^{\ast}||^2]\leq\\ &\inf_{\beta\neq 0}\{||X\beta^{\ast}-X\beta||^2+|\mathscr{K}(\beta)|[1+\log(\frac{M}{\mathscr{K}(\beta)})]\sigma^2\\ &+\sum_{k\in g} |\mathscr{J}_{k}(\beta)|[1+\log(\frac{p}{M|\mathscr{J}_{k}(\beta)|})]\sigma^2\} \end{align}

Comparing this result to the bound found for Group-sparse setting, we notice that the term $|\mathscr{J}_{k}(\beta)|p/M$ has been replaced by $\sum_{k\in g} |\mathscr{J}_{k}(\beta)|[1+\log(\frac{p}{M|\mathscr{J}_{k}(\beta)|})]$, that can potentially be way smaller if we ever had $|\beta|_{0}<<|\mathscr{J}_{k}(\beta)|p/M$. This last case represents the situation in which we would have a number of active coordinates much smaller than the total number of active coordinates if all the coordinates of our groups were active, ie. the Group-sparse setting. What this means is that in that case, we should better use the Sparse group-sparse setting, which is logical as we would not be accurate enough with only Group sparse setting.