The Benefit of Group Sparsity

Introduction

where we assume that the target coefficient ${\bar{\beta}}$ is sparse. Throughout the paper, we consider fixed design only. That is, we assume $X$ is fixed, and randomization is with respect to the noise $\epsilon$. Note that we do not assume that the noise $\epsilon$ is zero-mean.

where $k$ is the sparsity. Since this optimization problem is generally NP-hard, in practice, one often consider the following $L_{1}$ regularization problem, which is the closest convex relaxation of $L_{0}$:

where $\lambda$ is an appropriately chosen regularization parameter. This method is often referred to as Lasso in the statistical literature.

In practical applications, one often knows a group structure on the coefficient vector $\bar{\beta}$ so that variables in the same group tend to be zeros or nonzeros simultaneously. The purpose of this paper is to show that if such a structure exists, then better results can be obtained.

Strong Group Sparsity

For simplicity, we shall only consider non-overlapping groups in this paper, although our analysis can be adapted to handle moderately overlapping groups.

Assume that $\{1,\ldots,p\}=\cup_{j=1}^{m}G_{j}$ is partitioned into $m$ disjoint groups $G_{1},G_{2},\ldots,G_{m}$: $G_{i}\cap G_{j}=\emptyset$ when $i\neq j$. Moreover, throughout the paper, we let $k_{j}=|G_{j}|$, and $k_{0}=\max_{j\in\{1,\ldots,m\}}k_{j}$. Given $S\subset\{1,\ldots,m\}$ that denotes a set of groups, we define $G_{S}=\cup_{j\in S}G_{j}$.

The following method, often referred to as group Lasso, has been proposed to take advantage of the group structure:

The purpose of this paper is to develop a theory that characterizes the performance of (1). We are interested in conditions under which group Lasso yields better estimate of ${\bar{\beta}}$ than the standard Lasso.

Instead of the standard sparsity assumption, where the complexity is measured by the number of nonzero coefficients $k$, we introduce the strong group sparsity concept below. The idea is to measure the complexity of a sparse signal using group sparsity in addition to coefficient sparsity.

The new concept is referred to as strong group-sparsity because $k$ is used to measure the sparsity of ${\bar{\beta}}$ instead of $\|{\bar{\beta}}\|_{0}$. If this notion is beneficial, then $k/\|{\bar{\beta}}\|_{0}$ should be small, which means that the signal has to be efficiently covered by the groups. In fact, the group Lasso method does not work well when $k/\|{\bar{\beta}}\|_{0}$ is large. In that case, the signal is only weak group sparse, and one needs to use $\|{\bar{\beta}}\|_{0}$ to precisely measure the real sparsity of the signal. Unfortunately, such information is not included in the group Lasso formulation, and there is no simple fix of this problem using variations of group Lasso. This is because our theory requires that the group Lasso regularization term is strong enough to dominate the noise, and the strong regularization causes a bias of the order $O(k)$ which cannot be removed. This is one fundamental drawback which is inherent to the group Lasso formulation.

Related Work

The idea of using group structure to achieve better sparse recovery performance has received much attention. For example, group sparsity has been considered for simultaneous sparse approximation and multi-task compressive sensing from the Bayesian hierarchical modeling point of view. Under the Bayesian hierarchical model framework, data from all sources contribute to the estimation of hyper-parameters in the sparse prior model. The shared prior can then be inferred from multiple sources. Although the idea can be justified using standard Bayesian intuition, there are no theoretical results showing how much better (and under what kind of conditions) the resulting algorithms perform.

In , the authors attempted to derive a bound on the number of samples needed to recover block sparse signals, where the coefficients in each block are either all zero or all nonzero. In our terminology, this corresponds to the case of group sparsity with equal size groups. The algorithm considered there is a special case of (1) with $\lambda_{j}\to 0^{+}$. However, their result is very loose, and does not demonstrate the advantage of group Lasso over standard Lasso.

In the statistical literature, the group Lasso (1) has been studied by a number of authors . There were no theoretical results in . Although some theoretical results were developed in , neither showed that group Lasso is superior to the standard Lasso.

The authors of showed that group Lasso can be superior to standard Lasso when each group is an infinite dimensional kernel, by using an argument completely different from ours (they relied on the fact that meaningful analysis can be obtained for kernel methods in infinite dimension). Their idea cannot be adapted to show the advantage of group Lasso in finite dimensional scenarios of interests such as in the standard compressive sensing setting. Therefore our analysis, which focuses on the latter, is complementary to their work.

Another related work is , where the authors considered a special case of group Lasso in the multi-task learning scenario, and showed that the number of samples required for recovering the exact support set may be smaller for group Lasso under appropriate conditions. However, there are major differences between our analysis and their analysis. For example, the group formulation we consider here is more general and includes the multi-task scenario as a special case. Moreover, we study signal recovery performance in 2-norm instead of the exact recovery of support set in their analysis. The sparse eigenvalue condition employed in this work is often considerably weaker than the irrepresentable type condition in their analysis (which is required for exact support set recovery). Our analysis also shows that for strongly group-sparse signals, even when the number of samples is large, the group Lasso can still have advantages in that it is more robust to noise than standard Lasso.

In the above context, the main contribution of this work is the introduction of the strong group sparsity concept, under which a satisfactory theory of group Lasso is developed. Our result shows that strongly group sparse signals can be estimated more reliably using group Lasso, in that it requires fewer number of samples in the compressive sensing setting, and is more robust to noise in the statistical estimation setting.

Finally, we shall mention that independent of the authors, results similar to those presented in this paper have also been obtained in with a similar technical analysis. However, while our paper studies the general group Lasso formulation, only the special case of multi-task learning is considered in .

Assumptions

The following assumption on the noise is important in our analysis. It captures an important advantage of group Lasso over standard Lasso under the strong group sparsity assumption.

There exist non-negative constants $a,b$ such that for any fixed group $j\in\{1,\ldots,m\}$, and $\eta\in(0,1)$: with probability larger than $1-\eta$, the noise projection to the $j$-th group is bounded by:

The importance of the assumption is that the concentration term $\sqrt{-\ln\eta}$ does not depend on $k$. This reveals a significant benefit of group Lasso over standard Lasso: that is, the concentration term does not increase when the group size increases. This implies that if we can correctly guess the group sparsity structure, the group Lasso estimator is more stable with respect to stochastic noise than the standard Lasso.

Consider a $(g,k)$ strongly group sparse coefficient vector ${\bar{\beta}}$ such that

The last assumption is a sparse eigenvalue condition, used in the modern analysis of Lasso (e.g., ). It is also closely related to (and slightly weaker than) the RIP (restricted isometry property) assumption in the compressive sensing literature. This assumption takes advantage of group structure, and can be considered as (a weaker version of) group RIP. We introduce a definition before stating the assumption.

Moreover, for all $1\leq s\leq p$, define

Assumption 4.3 illustrates another advantage of group Lasso over standard Lasso. Since we only consider eigenvalues for sub-matrices consistent with the group structure $\{G_{j}\}$, the ratio $\rho_{+}(s)/\rho_{-}(s)$ can be significantly smaller than the corresponding ratio for Lasso (which considers all subsets of $\{1,\ldots,p\}$ up to size $s$). For example, assume that all group sizes are identical $k_{1}=\ldots=k_{m}=k_{0}$, and $s$ is a multiple of $k_{0}$. For random projections used in compressive sensing applications, only $n=O(s+(s/k_{0})\ln m)$ projections are needed for Assumption 4.3 to hold. In comparison, for standard Lasso, we need $n=O(s\ln p)$ projections. The difference can be significant when $p$ and $k_{0}$ are large. More precisely, we have the following random projection sample complexity bound for the group sparse eigenvalue condition. Although we assume Gaussian random matrix in order to state explicit constants, it is clear that similar results hold for other sub-Gaussian random matrices.

Suppose that elements in $X$ are iid standard Gaussian random variables $N(0,1)$. For any $t>0$ and $\delta\in(0,1)$, let

Main Results

Our main result is the following signal recovery (2-norm parameter estimation error) bound for group Lasso.

Suppose that Assumption 4.1, Assumption 4.2, and Assumption 4.3 are valid. Take $\lambda_{j}=(A\sqrt{k_{j}}+B)/\sqrt{n}$, where both $A$ and $B$ can depend on data ${\mathbf{y}}$. Given $\eta\in(0,1)$, with probability larger than $1-\eta$, if the following conditions hold:

$A\geq 4\max_{j}\rho_{+}(G_{j})^{1/2}(a+\delta a\sqrt{n})$,

$B\geq 4\max_{j}\rho_{+}(G_{j})^{1/2}(b\sqrt{\ln(m/\eta)}+\delta b\sqrt{n})$,

$\bar{\beta}$ is a $(g,k)$ strongly group-sparse coefficient vector,

In comparison, The Lasso estimator can only achieve the bound

If $k/\|{\bar{\beta}}\|_{0}\ll\ln(p/\eta)$ (which means that the group structure is useful) and $g\ll\|{\bar{\beta}}\|_{0}$, then the group Lasso is superior. This is consistent with intuition. However, if $k\gg\|{\bar{\beta}}\|_{0}\ln(p/\eta)$, then group Lasso is inferior. This happens when the signal is not strongly group sparse.

In the following, we present two simplifications of Theorem 5.1 that are easier to interpret. The first is the compressive sensing case, which does not consider stochastic noise.

If we have even sized groups, the number of samples $n$ required for Corollary 5.1 to hold (that is, $(\rho_{+}(s)-\rho_{-}(2s))/\rho_{-}(s)\leq 1/\sqrt{72}$) is $O(k+g\ln(m/g))$, where $g=k/k_{0}$. In comparison, although a similar result holds for Lasso, it requires sample size of order $\|{\bar{\beta}}\|_{0}\ln(p/\|{\bar{\beta}}\|_{0})$. Again, group Lasso has a significant advantage if $k/\|{\bar{\beta}}\|_{0}\ll\ln(p/\|{\bar{\beta}}\|_{0})$, $g\ll\|{\bar{\beta}}\|_{0}$, and $p$ is large.

The following corollary is for even sized groups, and the result is simpler to interpret. For standard Lasso, $B=O(\sqrt{\ln p})$, and for group Lasso, $B=O(\sqrt{\ln m})$. The benefit of group Lasso is the division of $B^{2}$ by $k_{0}$ in the bound, which is a significant improvement when the dimensionality $p$ is large. The disadvantage of group Lasso is that the signal sparsity $\|{\bar{\beta}}\|_{0}$ is replaced by the group sparsity $k$. This is not an artifact of our analysis, but rather a fundamental drawback inherent to the group Lasso formulation. The effect is observable, as shown in our simulation studies.

Suppose that Assumption 4.1 and Assumption 4.2 are valid. Assume also that all groups are of equal sizes: $k_{0}=k_{j}$ for $j=1,\ldots,m$. Given $\eta\in(0,1)$, let

where $A\geq 4\max_{j}\rho_{+}(G_{j})^{1/2}(a+\delta a\sqrt{n})$ and $B\geq 4\max_{j}\rho_{+}(G_{j})^{1/2}(b\sqrt{\ln(m/\eta)}+\delta b\sqrt{n})$. Let $\bar{\beta}$ be a $(k,k/k_{0})$ strongly group-sparse signal. With probability larger than $1-\eta$, if

Simulation Studies

We want to verify our theory by comparing group Lasso to Lasso on simulation data. For quantitative evaluation, the recovery error is defined as the relative difference in 2-norm between the estimated sparse coefficient vector $\beta_{est}$ and the ground-truth sparse coefficient ${\bar{\beta}}$: $\|\beta_{est}-{\bar{\beta}}\|_{2}/\|{\bar{\beta}}\|_{2}$.

The regularization parameter $\lambda$ in Lasso is chosen with five-fold cross validation. In group Lasso, we simply suppose the regularization parameter $\lambda_{j}=(\lambda\sqrt{k_{j}})/\sqrt{n}$ for $j=1,2,...,m$. The regularization parameter $\lambda$ is then chosen with five-fold cross validation. Here we set $B=0$ in the formula $\lambda_{j}=O(A\sqrt{k_{j}}+B)$. Since the relative performance of group Lasso versus standard Lasso is similar with other values of $B$, in order to avoid redundancy, we do not include results with $B\neq 0$.

In this set of experiments, the projection matrix $X$ is generated by creating an $n\times p$ matrix with i.i.d. draws from a standard Gaussian distribution $N(0,1)$. For simplicity, the rows of $X$ are normalized to unit magnitude. Zero-mean Gaussian noise with standard deviation $\sigma=0.01$ is added to the measurements. Our task is to compare the recovery performance of Lasso and Group Lasso for these $(g,k)$ strongly group sparse signals.

In this experiment, we randomly generate $(g,k)$ strongly group sparse coefficients with values $\pm 1$, where $p=512$, $k=64$ and $g=16$. There are 128 groups with even group size of $k_{0}=4$. Here the group structure coincides with the signal sparsity: $k=\|{\bar{\beta}}\|_{0}$.

Figure 1 shows an instance of generated sparse coefficient vector and the recovered results by Lasso and group Lasso respectively when $n=3k=192$. Since the sample size $n$ is only three times the signal sparsity $k$, the standard Lasso does not achieve good recovery results, whereas the group Lasso achieves near perfect recovery of the original signal.

Figure 2 shows the effect of sample size $n$, where we report the averaged recover error over 100 random runs for each sample size. Group Lasso is clearly superior in this case. These results show that the the group Lasso can achieve better recovery performance for $(g,k)$ strongly group sparse signals with fewer measurements, which is consistent with our theory.

To study the effect of the group number $g$ (with $k$ fixed), we set the sample size $n=160$ and then change the group number while keeping other parameters unchanged. Figure 2 shows the recovery performance of the two algorithms, averaged over 100 random runs for each sample size. As expected, the recovery performance for Lasso is independent to the group number within statistical error. Moreover, the recovery results for group Lasso are significantly better when the group number $g$ is much smaller than the sparsity $k=64$. When $g=k$, the group Lasso becomes identical to Lasso, which is expected. This shows that the recovery performance of group Lasso degrades when $g/k$ increases, which confirms our theory.

1.2 With incorrect group structure

In this experiment, we assume that the known group structure is not exactly the same as the sparsity of the signal (that is, $k>\|{\bar{\beta}}\|_{0}$). We randomly generate strongly group sparse coefficients with values $\pm 1$, where $p=512$, $\|{\bar{\beta}}\|_{0}=64$ and $g=16$. In the first experiment, we let $k=4\|{\bar{\beta}}\|_{0}$, and use $m=32$ groups with even group size of $k_{0}=16$.

Figure 3 shows one instance of the generated sparse signal and the recovered results by Lasso and group Lasso respectively when $n=3\|{\bar{\beta}}\|_{0}=192$. In this case, the standard Lasso obtains better recovery results than the group Lasso. Figure 2 shows the effect of sample size $n$, where we report the averaged recover error over 100 random runs for each sample size. The group Lasso recovery performance is clearly inferior to that of the Lasso. This shows that group Lasso fails when $k/\|{\bar{\beta}}\|_{0}$ is relatively large, which is consistent with our theory.

To study the effect of $k/\|{\bar{\beta}}\|_{0}$ on the group Lasso performance, we keep $\|{\bar{\beta}}\|_{0}$ fixed, and simply vary the group size as $k_{0}=1,2,4,8,16,32,64$ with $k/\|{\bar{\beta}}\|_{0}=1,1,1,2,4,8,16$. Figure 4 shows the performance of the two algorithms with different group sizes $k_{0}$ in terms of recovery error. It shows that the performance of group Lasso is better when $k/\|{\bar{\beta}}\|_{0}=1$. However, when $k/\|{\bar{\beta}}\|_{0}>1$, the performance of group Lasso deteriorates.

2 Uneven group size

In this set of experiments, we randomly generate $(g,k)$ strongly sparse coefficients with values $\pm 1$, where $p=512$, and $g=4$. There are 64 uneven sized groups. The projection matrix $X$ and noises are generated as in the even group size case. Our task is to compare the recovery performance of Lasso and Group Lasso for $(g,k)$ strongly sparse signals with $\|{\bar{\beta}}\|_{0}=k$. To reduce the variance, we run each experiment 100 times and report the average performance.

In the first experiment, the group sizes of $64$ groups are randomly generated and the $g=4$ active groups are randomly extracted from these $64$ groups. Figure 5 shows the recovery performance of Lasso and group Lasso with increasing sample size (measurements) in terms of recovery error. Similar to the case of even group size, the group Lasso obtains better recovery results than those with Lasso. It shows that the group Lasso is superior when the group sizes are randomly uneven.

As discussed after Theorem 5.1, because group Lasso favors large sized groups, if the signal is contained in small sized groups, then the performance of group Lasso can be relatively poor. In order to confirm this claim of Theorem 5.1, we consider the special case where $32$ groups have large group sizes and each of the remaining $32$ groups has only one element. First, we consider the case where half of $g=4$ active groups are extracted from the single element groups and the other half of $g=4$ active groups are extracted from the groups with large size. Figure 5 shows the signal recovery performance of Lasso and group Lasso. It is clear that the group Lasso performs better, but the results are not as good as those of Figure 5.

Moreover, Figure 6 shows the recovery performance of Lasso and group Lasso when all of the $g=4$ active groups are extracted from large sized groups. We observe that the relative performance of group Lasso improves. Finally, Figure 6 shows the recovery performance of Lasso and group Lasso when all of the $g=4$ active groups are extracted from single element groups. It is obvious that the group Lasso is inferior to Lasso in this case. This confirms the prediction of Theorem 5.1 that suggests that group Lasso favors large sized groups.

Conclusion

In this paper we introduced a concept called strong group sparsity that characterizes the signal recovery performance of group Lasso. In particular, we showed that group Lasso is superior to standard Lasso when the underlying signal is strongly group-sparse:

Group Lasso is more robust to noise due to the stability associated with group structure.

Group Lasso requires a smaller sample size to satisfy the sparse eigenvalue condition required in the modern sparsity analysis.

However, group Lasso can be inferior if the signal is only weakly group-sparse, or covered by groups with small sizes. Moreover, group Lasso does not perform well with overlapping groups (which is not analyzed in this paper). Better learning algorithms are needed to overcome these limitations.

References

Appendix A Proof of Proposition 4.1

Without loss of generality, we may assume $\sigma_{i}>0$ for all $i$ (otherwise, we can still let $\sigma_{i}>0$ and then just take the limit $\sigma_{i}\to 0$ for some $i$).

Therefore, we only need to show that with probability at least $1-\eta$ for all $\eta\in(0,1)$:

To prove this inequality, we note that the condition $Z^{\top}\Sigma Z=I_{k\times k}$ means that the covariance matrix of $\xi$ is $I_{k\times,k}$. Therefore the components of $\xi$ are $k$ iid Gaussians $N(0,1)$, and the distribution of $\|\xi\|_{2}^{2}$ is $\chi^{2}$. Many methods have been suggested to approximate the tail probability of $\chi^{2}$ distribution. For example, a well-known approximation of $\|\xi\|_{2}$ is the normal $N(\sqrt{k-0.5},0.5)$, which would imply $a=b=1$ in (3). In the following, we derive a slightly weaker tail probability bound using direct integration of tail probability for $\delta\geq\sqrt{k}$:

This implies that (3) holds with $a=1$ and $b=\sqrt{2}$.

Note that in the above derivation, we have used the following Sterling lower bound for the Gamma function

Appendix B Proof of Proposition 4.2

Appendix C Proof of Proposition 4.3

The following lemma is taken from . Since the proof is simple, it is included for completeness.

which implies that $|Q|\leq(1+2/\varepsilon)^{k}$.

The following concentration result for $\chi^{2}$ distribution is similar to Proposition 4.1. This is where the Gaussian assumption is used in the proof. A similar result holds for sub-Gaussian random variables.

Using identical derivation in the proof of Proposition 4.1, and let $\delta=\sqrt{n}-\epsilon$ and $k=n$, we obtain:

Combining the above two inequalities, we obtain the desired bound.

The derivation of the following estimate employs a standard proof technique (for example, see ).

Suppose $X$ is generated according to Proposition 4.3. For any fixed set $S\subset\{1,\ldots,p\}$ with $|S|=k$ and $0<\delta<1$, we have with probability exceeding $1-3(1+8/\delta)^{k}e^{-n\delta^{2}/8}$:

Proof It is enough to prove the conclusion in the case of $\|\beta\|_{2}=1$. According to Lemma C.1, given $\epsilon_{1}>0$, there exists a finite set $Q=\{q_{i}\}$ with $|Q|\leq(1+2/\epsilon_{1})^{k}$ such that $\|q_{i}\|_{2}=1$ for all $i$, and $\min_{i}\|\beta-q_{i}\|_{2}\leq\epsilon_{1}$ for all $\|\beta\|_{2}=1$.

For each $i$, Since elements of $\xi=X_{S}q_{i}$ are iid Gaussians $N(0,1)$, Lemma C.2 implies that $\forall\epsilon_{2}>0$:

Taking union bound for all $q_{i}\in Q$, we obtain with probability exceeding $1-3(1+2/\epsilon_{1})^{k}e^{-n\epsilon_{2}^{2}/2}$: for all $q_{i}\in Q$,

Now, we define $\rho$ as the smallest nonnegative number such that

where we used (5) in the derivation. Since $\rho$ is the smallest non-negative constant for which (5) holds, we have

Now we choose $\epsilon_{1}=\delta/4$ and $\epsilon_{2}=\delta/2$. Since $0<\delta<1$, it is easy to see that $\rho\leq\delta$. This proves the upper bound. For the lower bound, we note that for all $\|\beta\|_{2}=1$ with $\|\beta-q_{i}\|_{2}\leq\epsilon_{1}$, we have

with probability exceeding $1-3(1+8/\delta)^{k}e^{-n\delta^{2}/8}$.

Since the number of such groups $S$ can be no more than $C_{m}^{g}\leq(em/g)^{g}$, by taking the union bound, we know that the group RIP in Equation (2) fails with probability less than

Appendix D Technical Lemmas

The following lemmas are adapted from to handle group sparsity structure. Similar techniques can be found in . The first lemma is in . The proof is included for completeness.

Let $A=X^{\top}X/n$, and let $I$ and $J$ be non-overlapping indices in $\{1,\ldots,p\}$. We have

where the matrix 2-norm is defined as $\|A_{I,J}\|_{2}=\sup_{\|u\|_{2}=\|v\|_{2}=1}|u^{\top}A_{I,J}v|$.

The next lemma uses the previous result to control the contribution of the non-signal part $G^{c}$ of an error vector $u$ to the product $u_{G}^{\top}A_{G,G^{c}}u_{G^{c}}$.

This proves the first inequality of the lemma. Similarly, we have

Note that Lemma D.1 is used to bound $\|X_{G}^{\top}X_{G^{k}}\|_{2}$. This proves the second inequality of the lemma.

The following lemma shows that the group $L_{1}$-norm of the group Lasso estimator’s non-signal part is small (compared to the group $L_{1}$-norm of the parameter estimation error in the signal part).

By multiplying both sides by $({\hat{\beta}}-{\bar{\beta}})^{\top}$, we obtain

Note that the last inequality follows from the assumption of the lemma. By simplifying the above inequality, we obtain the desired bound.

The following lemma bounds parameter estimation error by combining the previous two lemmas.

Proof Define $S_{0}$ as in Lemma D.2. Let $G=\cup_{j\in S\cup S_{0}}G_{j}$. By multiplying both sides of (6) by $({\hat{\beta}}-{\bar{\beta}})_{G}^{\top}$, we obtain

Similar to the proof in Lemma D.3, we use the assumptions on $\lambda_{j}$ to obtain:

The assumption of the lemma is used to derive the last inequality. Now plug this inequality into (7), we have

By combining the previous two displayed inequalities, we obtain the lemma.

Appendix E Proof of Theorem 5.1

Assumption 4.1 implies that with probability larger than $1-\eta$, uniformly for all groups $j$, we have

Note that we have used $\sum_{j\in S^{\prime}}[A^{2}k_{j}+B^{2}]\leq n\sum_{j\in S^{\prime}}\lambda_{j}^{2}\leq 2\sum_{j\in S^{\prime}}[A^{2}k_{j}+B^{2}]$.

Therefore the conditions of Lemma D.4 are satisfied. Its conclusion implies that