Group Lasso with Overlaps: the Latent Group Lasso approach

Introduction

The corresponding decomposition of a parameter vector into latent variables calls for the notion of group-support, which we introduce and which corresponds to the set of non-zero latent variables. In the context of a learning problem regularized by the norm we propose, we study the problem of group-support recovery, a notion stronger than the classical support recovery. Group-support recovery typically implies support recovery (although not always) if the support of a parameter vector is exactly a union of groups. We provide sufficient conditions for consistent group-support recovery.

In the definition of our norm, a weight is associated with each group. These weights play a much more important role in the case of overlapping groups than in the case of disjoint groups, since in the former case they determine the set of recoverable supports and the complexity of the class of possible models. We discuss the delicate question of the choice of these weights.

While the norm we consider is quite general and has potentially many applications, we illustrate its potential on the particular problem of learning sparse predictive models for cancer prognosis from high-dimensional gene expression data. The problem of identifying a predictive molecular signature made of a small set of genes is often ill-posed and so noisy that exact variable selection may be elusive. We propose that, instead, selecting genes in groups that are involved in the same biological process or connected in a functional or interaction network could be performed more reliably, and potentially lead to better predictive models. We empirically explore this application, after extensive experiments on simulated data illustrating some of the properties of our norm.

To summarize, the main contributions of this paper, which rephrases and extends a preliminary version published in Jacob et al. (2009), are the following:

We define the latent group Lasso penalty to infer sparse models with unions of predefined groups as supports, and analyze in details some of its mathematical properties.

We introduce the notion of group-support and group-support recovery results. Using correspondence theory, we show under appropriate conditions, that, in a classical asymptotic setting, estimators for the linear regression regularized with $\Omega_{\cup}^{\mathcal{G}}$ are consistent for the estimation of a sufficiently sparse group-support.

We discuss in length the choice of weights associated to each group, which play a crucial role in the presence of overlapping groups of different sizes.

We provide extended experimental results both on simulated data — addressing support-recovery, estimation error and role of weights — and on breast cancer data, using biological pathways and genes networks as prior information to construct latent group Lasso formulations.

The rest of the paper is structured as follows. We first introduce the latent group Lasso penalty and position it in the context of related work in Section 3. In Section 4 we show that it is a norm and provide several characterizations and variational formulations; we also show that regularizing with this norm is equivalent to covariate duplication (Section 4.6) and derive a corresponding multiple kernel learning formulation (Section 4.7). We briefly discuss algorithms in Section 4.8. In Section 5, we introduce the notion of group-support and consider in Section 6 a few toy examples to illustrate the concepts and properties discussed so far. We study group support-consistency in Section 7. The difficult question of the choice of the weighting scheme is discussed in Section 8. Section 9 presents the latent graph Lasso, a variant of the latent group Lasso when covariates are organized into a graph. Finally, in Section 10, we present several experiments: first, on artificial data to illustrate the gain in support recovery and estimation over the classical Lasso, as well as the influence of the choice of the weights; second, on the real problem of breast cancer prognosis from gene expression data.

Notations

Throughout the article, $\mathcal{G}\subset\mathcal{P}([1,p])$ denotes a set of groups, usually fixed in advance for each application, and we denote $m\overset{\,\Delta}{=}|\mathcal{G}|$ the number of groups in $\mathcal{G}$. We require that all covariates belong to at least one group, i.e.,

Group Lasso with overlapping groups

often leads to a solution that lies on a singularity, i.e., to a vector $\mathbf{w}$ such that $\mathbf{w}_{g}=\mathbf{0}$ for some of the groups $g$ in $\mathcal{G}$. Equivalently, the solution is sparse at the group level, in the sense that coefficients within a group are usually zero or nonzero together. The hyperparameter $\lambda\geq 0$ in (2) is used to adjust the tradeoff between minimizing the loss and finding a solution which is sparse at the group level.

When $\mathcal{G}$ is not a partition anymore and some of its groups overlap, the penalty (1) is still a norm, because we assume that all covariates belong to at least one group. However, while the Lasso is sometimes loosely presented as selecting covariates and the group Lasso as selecting groups of covariates, the group Lasso estimator (2) does not necessarily select groups in that case. The reason is that the precise effect of non-differentiable penalties is to set covariates, or groups of covariates, to zero, and not to select them. When there is no overlap between groups, setting groups to zero leaves the other full groups to nonzero, which can give the impression that group Lasso is generally appropriate to select a small number of groups. When the groups overlap, however, setting one group to zero shrinks its covariates to zero even if they belong to other groups, in which case these other groups will not be entirely selected. This is illustrated in Figure 1(a) with three overlapping groups of covariates. If the penalty leads to an estimate in which the norm of the first and of the third group are zero, what remains nonzero is not the second group, but the covariates of the second group which are neither in the first nor in the third one. More formally, the overlapping case has been extensively studied by Jenatton et al. (2009), who showed that in the case where $L(\mathbf{w})$ is an empirical risk and under very general assumptions on the data, the support of a solution $\hat{\mathbf{w}}$ of (2) almost surely satisfies

for some $\mathcal{G}_{0}\subset\mathcal{G}$, i.e., the support is almost surely the complement of a union of groups. Equivalently, the support is an intersection of the complements of some of groups considered.

In other words, this formulation leads to sparse solutions whose support is likely to be a union of groups.

Interestingly, problem (3) can be reformulated as the minimization of the cost function $L(\mathbf{w})$ penalized by a new regularizer which is a function of $\mathbf{w}$ only. Indeed since the minimization over $\mathbf{\bar{v}}$ only involves the penalty term and the constraints, we can rewrite (3) as

To summarize, we enforce a prior we have on $\mathbf{w}$ by introducing new variables in the optimization problem (3). The constraint we impose is that some groups should be shrunk to zero, and a covariate should have zero weight in $\mathbf{w}$ if all the groups to which it belongs are set to zero. Equivalently, the support of $\mathbf{w}$ should be a union of groups. This new problem can be re-written as a classical minimization of the empirical risk, penalized by a particular penalty $\Omega_{\cup}^{\mathcal{G}}$ defined in (5). This penalty itself associates to each vector $\mathbf{w}$ the solution of a particular constrained optimization problem. While this formulation may not be the most intuitive, it allows to reframe the problem in the classical context of penalized empirical risk minimization. In the remaining of this article, we investigate in more details the latent group Lasso penalty $\Omega_{\cup}^{\mathcal{G}}$, both theoretically and empirically.

$\Omega^{\mathcal{G}}_{0}$ can then be interpreted as the value of a min set-cover. This penalization has been considered in Huang et al. (2009) under the name block coding, since, indeed, when $d_{g}$ is interpreted as a coding length, this penalization induces a code length on all sets, which can be interpreted in the MDL framework.

It should be noted that recent theoretical analyses of the norm studied in this paper have been proposed by Percival (2011) and Maurer and Pontil (2011). They adopt points of views or focus on questions that are complementary of this work; we discuss those in section 7.3.

Some properties of the latent group Lasso penalty

In this section we study a few properties of the latent group Lasso $\Omega_{\cup}^{\mathcal{G}}$, which will be in particular useful to prove consistency results in the next section. After showing that $\Omega_{\cup}^{\mathcal{G}}$ is a valid norm, we compute its dual norm and provide two variational formulas. We then characterize its unit ball as the convex hull of basic disks, and compute its subdifferential. When used as a penalty for statistical inference, we further reinterpret it in the context of covariate duplication and multiple kernel learning. To lighten notations, in the rest of the paper we simply denote $\Omega_{\cup}^{\mathcal{G}}$ by $\Omega$.

Proof The objective of problem (5) is a proper closed convex function with no direction of recession. Lemma 1 is then the consequence of classical results in convex analysis, such as Theorem 27.2 page 265 of Rockafellar (1997). The following statement shows that, unsurprisingly, we can regard $\Omega$ as a classical norm-based penalty.

$\mathbf{w}\mapsto\Omega(\mathbf{w})$ is a norm.

2 Dual norm and variational characterizations

$\Omega$ being a norm, by Lemma 1, we can consider its Fenchel dual norm $\Omega^{*}$ defined by:

The following lemma shows that $\Omega^{*}$ has a simple closed form expression:

The Fenchel dual norm $\Omega^{*}$ of $\Omega$ satisfies:

Proof We start from the definition of the dual norm (6) and compute:

The second equality is due to the fact that :

and the fifth results from the explicit solution $\mathbf{v}^{g}=\boldsymbol{\alpha}_{g}\eta_{g}d_{g}^{-1}\left\|\boldsymbol{\alpha}_{g}\right\|^{-1}$ of the maximization in $\mathbf{\bar{v}}$ in the fourth line.

The norm $\Omega$ was initially defined as the solution of an optimization problem in (5). From the characterization of $\Omega^{*}$ we can easily derive a second variational formulation:

Proof Since the bi-dual of a norm is the norm itself, we have the variational form

With a few more efforts, we can also derive a third variational representation of the norm $\Omega$, which will be useful in Section 7 in the proofs of consistency:

is a bijection from $\mathbf{V}(\mathbf{w})$ to $\boldsymbol{\Lambda}(\mathbf{w})$. For any $\boldsymbol{\lambda}\in\boldsymbol{\Lambda}(\mathbf{w})$, the only vector $\mathbf{\bar{v}}\in\mathbf{V}(\mathbf{w})$ that satisfies $\boldsymbol{\lambda}(\mathbf{\bar{v}})=\boldsymbol{\lambda}$ is given by $\mathbf{v}^{g}_{g}=\boldsymbol{\lambda}_{g}\boldsymbol{\alpha}_{g}$, where $\boldsymbol{\alpha}$ is any vector of $\mathcal{A}(\mathbf{w})$.

where for any $\mathbf{\bar{v}}$, the minimum in $\boldsymbol{\lambda}^{\prime}$ is uniquely attained for $\boldsymbol{\lambda}^{\prime}=\boldsymbol{\lambda}(\mathbf{\bar{v}})$ defined in (11). By definition of $\mathbf{V}(\mathbf{w})$, the set of solutions of (12) is therefore exactly the set of pairs of the form $\left(\mathbf{\bar{v}},\boldsymbol{\lambda}(\mathbf{\bar{v}})\right)$ for $\mathbf{\bar{v}}\in\mathbf{V}(\mathbf{w})$. Let us now isolate the minimization over $\mathbf{\bar{v}}$ in (12). To incorporate the constraint $\sum_{g\in\mathcal{G}}\mathbf{v}^{g}=\mathbf{w}$ we rewrite (12) with a Lagrangian:

The inner minimization in $\mathbf{\bar{v}}$, for fixed $\boldsymbol{\lambda}^{\prime}$ and $\boldsymbol{\alpha}^{\prime}$, yields $\mathbf{v}^{g}_{i}=\boldsymbol{\lambda}^{\prime}_{g}\boldsymbol{\alpha}^{\prime}_{i}$. The constraint $\mathbf{w}=\sum_{g\in\mathcal{G}}\mathbf{v}^{g}$ therefore implies that, after optimization in $\mathbf{\bar{v}}$ and $\boldsymbol{\alpha}^{\prime}$, we have $\boldsymbol{\alpha}^{\prime}_{i}=\frac{w_{i}}{\sum_{g\ni i}\boldsymbol{\lambda}^{\prime}_{g}}$, and as a consequence that $\mathbf{v}^{g}_{i}=\frac{\boldsymbol{\lambda}^{\prime}_{g}}{\sum_{h\ni i}\boldsymbol{\lambda}^{\prime}_{h}}\,\mathbf{w}_{i}$. A small computation now shows that, after optimization in $\mathbf{\bar{v}}$ and $\boldsymbol{\alpha}^{\prime}$ for a fixed $\boldsymbol{\lambda}^{\prime}$, we have:

Plugging this into (12), we see that after optimization in $\mathbf{\bar{v}}$, the optimization problem in $\boldsymbol{\lambda}^{\prime}$ is exactly (10), which by definition admits $\boldsymbol{\Lambda}(\mathbf{w})$ as solutions, while we showed that (12) admits $\boldsymbol{\lambda}\left(\mathbf{V}(\mathbf{w})\right)$ as solutions. This shows that $\boldsymbol{\lambda}\left(\mathbf{V}(\mathbf{w})\right)=\boldsymbol{\Lambda}(\mathbf{w})$, and since for any $\boldsymbol{\lambda}^{\prime}\in\boldsymbol{\Lambda}(\mathbf{w})$ there exists a unique $\mathbf{\bar{v}}\in\mathbf{V}(\mathbf{w})$ that satisfies $\boldsymbol{\lambda}(\mathbf{\bar{v}})=\boldsymbol{\lambda}^{\prime}$, namely, $\mathbf{v}^{g}_{i}=\frac{\boldsymbol{\lambda}^{\prime}_{g}}{\sum_{h\ni i}\boldsymbol{\lambda}^{\prime}_{h}}\,\mathbf{w}_{i}$, $\boldsymbol{\lambda}$ is indeed a bijection from $\mathbf{V}(\mathbf{w})$ to $\boldsymbol{\Lambda}(\mathbf{w})$. Finally, we noted in the proof of Lemma 6 that for any $\boldsymbol{\lambda}\in\boldsymbol{\Lambda}(\mathbf{w})$ and $\boldsymbol{\alpha}\in\mathcal{A}(\mathbf{w})$, $\mathbf{w}_{i}=\boldsymbol{\alpha}_{i}\sum_{h\ni i}\boldsymbol{\lambda}_{h}$. This shows that the unique $\mathbf{\bar{v}}\in\mathbf{V}(\mathbf{w})$ associated to a $\boldsymbol{\lambda}\in\boldsymbol{\Lambda}(\mathbf{w})$ can equivalently be written $\mathbf{v}_{g}^{g}=\boldsymbol{\lambda}_{g}\boldsymbol{\alpha}_{g}$, which concludes the proof of Lemma 7.

3 Characterization of the unit ball of ΩΩ\Omega as a convex hull

Figure 2(b) suggests visually that the unit ball of $\Omega$ is just the convex hull of a horizontal disk and a vertical one. This impression is correct and formalized more generally in the following lemma.

Conversely, if $\Omega(\mathbf{w})\leq 1$, then there exists $\mathbf{\bar{v}}\in\mathcal{V}_{\mathcal{G}}$, such that $\sum_{g\in\mathcal{G}}d_{g}\left\|\mathbf{v}^{g}\right\|\leq 1$ and we obtain $\boldsymbol{\alpha}^{g}\in\mathcal{D}_{g}$ and $\mathbf{t}$ in the simplex by letting $t_{g}=d_{g}\left\|\mathbf{v}^{g}\right\|$ and

It should be noted that this lemma shows that $\Omega$ is the gauge of the convex hull of the disks $\mathcal{D}_{g}$, in other words, $\Omega$ is, in the terminology introduced by Chandrasekaran et al. (2010), the unit ball of the atomic norm associated with the union of disks $\mathcal{D}_{g}$.

4 Subdifferential of ΩΩ\Omega

The subdifferential of $\Omega$ at $\mathbf{w}$ is, by definition:

We can now show a simple relationship between the decomposition $(\mathbf{v}^{g})_{g\in\mathcal{G}}$ of a vector $\mathbf{w}$ induced by $\Omega$, and the subdifferential of $\Omega$.

For any $\boldsymbol{\alpha}\in\mathcal{A}(\mathbf{w})=\partial\Omega(\mathbf{w})$ and any $\mathbf{\bar{v}}\in\mathbf{V}(\mathbf{w})$,

Proof Let $\mathbf{\bar{v}}\in\mathbf{V}(\mathbf{w})$ and $\boldsymbol{\alpha}\in\mathcal{A}(\mathbf{w})$. Since $\Omega^{*}(\boldsymbol{\alpha})\leq 1$, we have $\left\|\boldsymbol{\alpha}_{g}\right\|\leq d_{g}$ which implies $\boldsymbol{\alpha}^{\top}\mathbf{v}^{g}\leq d_{g}\left\|\mathbf{v}^{g}\right\|$. On the other hand, we also have $\boldsymbol{\alpha}^{\top}\mathbf{w}=\Omega(\mathbf{w})$ so that $0=\Omega(\mathbf{w})-\boldsymbol{\alpha}^{\top}\mathbf{w}=\sum_{g}\left(d_{g}\left\|\mathbf{v}^{g}\right\|-\boldsymbol{\alpha}_{g}^{\top}\mathbf{v}^{g}\right),$ which is a sum of non-negative terms. We conclude that, for all $g\in\mathcal{G}$, we have $\boldsymbol{\alpha}_{g}^{\top}\mathbf{v}^{g}=d_{g}\left\|\mathbf{v}^{g}\right\|$ which yields the result. We can deduce a general property of all decompositions of given vector:

Proof By Lemma 9, if $\mathbf{v}^{g}\neq\mathbf{0}$ and ${\mathbf{v}^{\prime}}^{g}\neq\mathbf{0}$, then $\boldsymbol{\alpha}_{g}=d_{g}\frac{\mathbf{v}^{g}}{\left\|\mathbf{v}^{g}\right\|}=d_{g}\frac{{\mathbf{v}^{\prime}}^{g}}{\left\|{\mathbf{v}^{\prime}}^{g}\right\|}$ so that $\mathbf{v}^{g}=\frac{\left\|\mathbf{v}^{g}\right\|}{\left\|{\mathbf{v}^{\prime}}^{g}\right\|}{\mathbf{v}^{\prime}}^{g}$.

5 ΩΩ\Omega as a regularizer

Its solutions are characterized by optimality conditions from subgradient calculus:

$-\nabla L(\mathbf{w})/\lambda\in\mathcal{A}(\mathbf{w})$

$\mathbf{w}$ can be decomposed as $\mathbf{w}=\sum_{g\in\mathcal{G}}\mathbf{v}^{g}$ for some $\bar{\mathbf{v}}\in\mathcal{V}_{\mathcal{G}}$ with for all $g\in\mathcal{G}$:

Proof (a) is immediate from subgradient calculus and the fact that $\partial\Omega(\mathbf{w})=\mathcal{A}(\mathbf{w})$ (see Section 4.4). (b) is immediate from Lemma 9.

6 Covariate duplication

In this section we show that empirical risk minimization penalized by $\Omega$ is equivalent to a regular group Lasso in a covariate space of higher dimension obtained by duplication of the covariates belonging to several groups. This has implications for practical implementation of $\Omega$ as a regularizer and for its generalization to non-linear classification.

More precisely, let us consider the duplication operator:

where $\mathbf{X}$ is the $n\times p$ matrix of training points and $\mathbf{X}\mathbf{w}$ is therefore the vector of inner products of $\mathbf{w}$ with the training points. Many problems, in particular those considered in Section 4.5, have this form. By definition of $\Omega$ we can rewrite (16) as

On the example of Figure 1,with $3$ overlapping groups, this duplication trick can be rewritten as follows :

7 Multiple Kernel Learning formulations

Given the reformulation in a duplicated variable space presented above, we provide in this section a multiple kernel learning (MKL) interpretation to the regularization by our norm and show that it extends naturally the case with disjoint groups.

To introduce it, we return first to the concept of MKL (Lanckriet et al., 2004; Bach et al., 2004) which we can present as follows. If one considers a learning problem of the form

then by the representer theorem the optimal value of the objective $H$ only depends on the input data $\mathbf{X}$ through the Gram matrix $\mathbf{K}=\mathbf{X}\mathbf{X}^{\top}$, which therefore can be replaced by any positive definite (p.d.) kernel between the datapoints. Moreover $H$ can be shown to be a convex function of $\mathbf{K}$ (Lanckriet et al., 2004). Given a collection of p.d. kernels $\mathbf{K}_{1},\ldots,\mathbf{K}_{k}$, any convex combination $\mathbf{K}=\sum_{i=1}^{k}\eta_{i}\mathbf{K}_{i}$ with $\eta_{i}\geq 0$ and $\sum_{i}\eta_{i}=1$ is itself a p.d. kernel. The multiple kernel learning problem consists in finding the best such combination in the sense of minimizing $H$:

The kernels considered in the linear combination above are typically reproducing kernels associated with different reproducing kernel Hilbert spaces (RKHS).

with $\mathbf{K}_{g}=\mathbf{X}_{g}\mathbf{X}_{g}^{\top}$, then $(P)$ and $(P^{\prime})$ are equivalent in the sense that the optimal values of both objectives are equal with a bijection between the optimal solutions. Note that such an equivalence does not hold if the groups $g\in\mathcal{G}$ overlap.

Conversely, it should be noted that, while one of the application of multiple kernel learning is data fusion and thus allows to combine kernels corresponding to functions of intrinsically different input variables, MKL can also be used to select and combine elements from different function spaces defined on the same input. In general these function spaces are not orthogonal and are typically not even disjoint. In that case the MKL formulation corresponds implicitly to using the norm presented in this paper.

This last formulation can be viewed as the structured MKL formulation associated with the norm $\Omega$ (see Bach et al., 2011, sec. 1.5.4). It is clearly more interesting computationally when $m\gg p$. It is however restricted to a particular form of kernel $\mathbf{K}_{g}$ for each group, which has to be a sum of feature kernels $\mathbf{K}_{i}$. In particular, it doesn’t allow for interactions among features in the group.

In the two formulations above, it is obviously possible to replace the linear kernel used for the derivation by a non-linear kernel. In the case of (21) the combinatorial structure of the problem is a priori lost in the sense that the different kernels are no longer linear combinations of a set of “primary” kernels, while this is still the case for (22).

Using non-linear kernels like RBF, or kernels on discrete structures such as sequence- or graph-kernels may prove useful in cases where the relationship between the covariates in the groups and the output is expected to be non-linear. For example if $g$ is a group of genes and the coexpression patterns of genes within the group are associated with the output, the group will be deemed important by a non linear kernel while a linear one may miss it. More generally, it allows for structured non-linear feature selection.

8 Algorithms

Alternatively, efficient algorithms which do not require working in the space of duplicated covariates are possible. Such an algorithm was proposed by Mosci et al. (2010) who suggested to use a proximal algorithm, and to compute the proximal operator of the norm $\Omega$ via an approximate projection on the unit ball of the dual norm in the input space. To avoid duplication, it would also be possible to use an approach similar to that of (Rakotomamonjy et al., 2008). Finally, one could also consider algorithms from the multiple kernel learning literature.

Group-support

A natural question associated with the norm $\Omega$ is what sparsity pattern are elicited when the norm is used as a regularizer. This question is natural in the context of support recovery. If the groups are disjoint, one could equivalently ask which patterns of selected group are possible, since answering the latter or the former questions are equivalent. This suggest a view in which the support is expressed in terms of groups. We formalize this idea through the concept of group-support of a vector $\mathbf{w}$, which, put informally, is the set of groups that are non-zero in a decomposition of $\mathbf{w}$. We will see that this notion is useful to characterize induced decompositions and recovery properties of the norm.

More formally, we naturally call group-support of a decomposition $\mathbf{\bar{v}}\in\mathcal{V}_{\mathcal{G}}$, the set of groups $g$ such that $\mathbf{v}^{g}\neq\mathbf{0}$. We extend this definition to a vector as follows:

If $\mathbf{w}$ has a unique decomposition $\mathbf{\bar{v}}(\mathbf{w})$, then $\breve{\mathcal{G}}_{1}(\mathbf{w})=\{g\in\mathcal{G}\,|\,\mathbf{v}^{g}(\mathbf{w})\neq\mathbf{0}\}$ is the group-support of its decomposition. We also define a notion of weak group-support in terms of uniqueness of the optimal dual variables.

It follows immediately from Lemma 9 that $\breve{\mathcal{G}}_{1}(\mathbf{w})\subset\mathcal{G}_{1}(\mathbf{w})$. When $\breve{\mathcal{G}}_{1}(\mathbf{w})=\mathcal{G}_{1}(\mathbf{w})$, we refer to $\breve{\mathcal{G}}_{1}(\mathbf{w})$ as the group-support of $\mathbf{w}$; otherwise we say that the group-support is ambiguous.

The definitions of strong group-support and weak group-support are motivated by the fact that in the variational formulation (8), the strong group-support is the set of groups for which the constraints $\left\|\boldsymbol{\alpha}_{g}\right\|\leq 1$ are strongly active whereas the weak group-support is the set of weakly or strongly active such constraints (Nocedal and Wright, 2006, p.342). We illustrate these two notions on a few examples in Section 6.

2 Supports induced by the group-support

Since $\breve{\mathcal{G}}_{1}(\mathbf{w})\subset\mathcal{G}_{1}(\mathbf{w})$, it immediately follows that $\breve{J}_{1}(\mathbf{w})\subset J_{1}(\mathbf{w})$It is possible to have $\breve{J}_{1}(\mathbf{w})\neq J_{1}(\mathbf{w})$ consider \mathcal{G}=\big{\{}\{1,2\},\{1,3\},\{2,3,4\}\big{\}} and $\mathbf{w}=\frac{1}{\sqrt{2}}(1,\mu,1-\mu,0)$ for any $\mu\in(0,1)$. We then have \breve{\mathcal{G}}_{1}=\big{\{}\{1,2\},\{1,3\}\big{\}} and $\mathcal{G}_{1}=\mathcal{G}$ so that $\breve{J}_{1}=\{1,2,3\}\neq J_{1}=\{1,2,3,4\}$.. The following two lemmas show that, on $J_{1}(\mathbf{w})$, any dual variables $\boldsymbol{\alpha}\in\mathcal{A}(\mathbf{w})$ are uniquely determined.

If $J_{1}(\mathbf{w})\backslash\breve{J}_{1}(\mathbf{w})\neq\varnothing$, then for any $\boldsymbol{\alpha}\in\mathcal{A}(\mathbf{w})$, $\boldsymbol{\alpha}_{J_{1}(\mathbf{w})\backslash\breve{J}_{1}(\mathbf{w})}=\mathbf{0}$.

Proof Note that $\mathbf{w}_{J_{1}(\mathbf{w})\backslash\breve{J}_{1}(\mathbf{w})}=\mathbf{0}$ since $\mathbf{v}^{g}=\mathbf{0}$ for $g\in\mathcal{G}_{1}(\mathbf{w})\backslash\breve{\mathcal{G}}_{1}(\mathbf{w})$. Let $g\in\mathcal{G}_{1}(\mathbf{w})\backslash\breve{\mathcal{G}}_{1}(\mathbf{w})$. If $g\backslash\breve{J}_{1}(\mathbf{w})\neq\varnothing$, and if $\Pi_{g\backslash\breve{J}_{1}(\mathbf{w})}\mathcal{A}(\mathbf{w})\neq\{\mathbf{0}\}$ then, let $i\in g\backslash\breve{J}_{1}(\mathbf{w})$ such that there exists $\boldsymbol{\alpha}\in\mathcal{A}(\mathbf{w})$ with $\boldsymbol{\alpha}_{i}\neq 0$. Setting $\boldsymbol{\alpha}_{i}=0$ leads to another vector that solves the second variational formulation (7) and such that $\left\|\boldsymbol{\alpha}_{g}\right\|<d_{g}$ which contradicts the hypothesis that $g\in\mathcal{G}_{1}(\mathbf{w})$.

Proof By definition of $\breve{J}_{1}(\mathbf{w})$, for all $i\in\breve{J}_{1}(\mathbf{w})$ there exists at least one $\mathbf{v}\in\mathbf{V}(\mathbf{w})$ and one group $g\ni i$, such that $(\mathbf{v}^{g})_{i}\neq 0$. Now as a consequence of Lemma 9, for any two solutions $\boldsymbol{\alpha},\boldsymbol{\alpha}^{\prime}\in\mathcal{A}(\mathbf{w})$, we have that $\boldsymbol{\alpha}_{g}=\boldsymbol{\alpha}^{\prime}_{g}=d_{g}\frac{\mathbf{v}^{g}}{\left\|\mathbf{v}^{g}\right\|}$, so in particular $\boldsymbol{\alpha}_{i}=\boldsymbol{\alpha}^{\prime}_{i}$. For $i\in J_{1}(\mathbf{w})\backslash\breve{J}_{1}(\mathbf{w})$, Lemma 14 shows that $\boldsymbol{\alpha}_{i}=0$.

Illustrative examples

In this section, we consider a few examples that illustrate some of the properties of $\Omega$, namely situations where weak and strong group support differ, or where there is an entire set of optimal decompositions. We will abuse notations and write $\mathbf{v}_{g}$ for $\mathbf{v}^{g}_{g}$ when writing explicit decompositions. We will denote by ${{\rm Sign}}$ the correspondence (or set-valued function) defined by ${\rm Sign}(x)={1}$ if $x>0$, ${\rm Sign}(x)={-1}$ if $x<0$ and ${\rm Sign}(0)=$.

We first consider the case $p=3$ and $\mathcal{G}=\{\{1,2\},\{2,3\}\}$.

We have $\Omega(\mathbf{w})=\left\|(w_{2},|w_{1}|+|w_{3}|)^{\top}\right\|$. If $(w_{1},w_{3})\neq\mathbf{0}$, the optimal decomposition is unique with

$J_{1}=\breve{J}_{1}=\text{supp}\left(\mathbf{w}\right)$ and $\mathcal{G}_{1}=\breve{\mathcal{G}}_{1}$ includes $\{w_{1},w_{2}\}$ if $w_{1}\neq 0$ and $\{w_{2},w_{3}\}$ if $w_{3}\neq 0$. If $(w_{1},w_{3})=\mathbf{0}$, then $\mathbf{v}_{\{12\}}=(0\>,\gamma\,w_{2})^{\top}\quad\text{and}\quad\mathbf{v}_{\{23\}}=(\,(1-\gamma)\,w_{2}\>,\>0)^{\top}$ is an optimal decomposition for any $\gamma\in$, $\mathcal{A}(\mathbf{w})=\{(0,\text{sign}(w_{2}),0)\}$, $J_{1}=\breve{J}_{1}=\{1,2,3\}$ and $\mathcal{G}_{1}=\breve{\mathcal{G}}_{1}=\mathcal{G}$.

We prove this lemma in section C.1.1 (as a special case of the “cycle of length three” which we consider next). Here, the case where the decomposition is not unique seems to be a relatively pathological case where the true support is included in the intersection of two groups. However, note that the weak group-support and strong-group support coincide, even in the latter case.

2 Cycle of length 3

We now turn to the case $p=3$ and $\mathcal{G}=\{\{1,2\},\{2,3\},\{1,3\}\}$. Note that if at least one of the groups is not part of the weak-group support, we fall back on the case of two overlapping groups. We therefore have the following lemma:

If $|\text{supp}\left(\mathbf{w}\right)|\neq 1$ the optimal decomposition is unique. If in addition, $\mathbf{w}\in\mathcal{W}_{\text{bal}}$ we have for $(i,j,k)\in\{(1,2,3),(2,3,1),(3,1,2)\}$:

Moreover, we have $J_{1}=\breve{J}_{1}=\{1,2,3\}$, $\mathcal{G}_{1}=\mathcal{G}$ and for $\mathbf{w}\in\mathring{\mathcal{W}}_{\text{bal}}$, $\mathcal{G}_{1}=\breve{\mathcal{G}}_{1}=\mathcal{G}$.

We prove this lemma in appendix C.1, and illustrate it on Figure 3 with the unit ball of the obtained norm. In this case it is interesting to note that the group-support (weak or strong) is not necessarily a minimal cover, where we say that a set of groups provides a minimal cover if it is impossible to remove a group while still covering the support. For instance, for $\mathbf{w}$ in the interior of $\mathcal{W}_{\text{bal}}$, the group-support contains all three groups, while the support is covered by any two groups. This is clearly a consequence of the convexity of the formulation. The cycle of length 3 is also interesting because, for any $\mathbf{w}$ on the boundary of $\mathcal{W}_{\text{bal}}$, the weak and strong group-support do not coincide, as illustrated on Figure 3 (right). Indeed if for example $|w_{3}|=|w_{1}|+|w_{2}|$, then $\mathbf{v}_{\{1,2\}}=(0,0)^{\top},\mathbf{v}_{\{1,3\}}=|w_{1}|(\text{sign}(w_{1}),\text{sign}(w_{3}))^{\top}$ and $\mathbf{v}_{\{2,3\}}=|w_{2}|(\text{sign}(w_{2}),\text{sign}(w_{3}))^{\top}$ so that by lemma 9 the dual variable satisfies $\left\|\boldsymbol{\alpha}_{\{1,2\}}\right\|=1$, which means that $\{1,2\}$ is in the weak but not in the strong group-support.

3 Cycle of length 4

We consider the case $p=4$ and show the following result in appendix C.2.

For \mathcal{G}=\big{\{}\{1,2\},\{1,3\},\{2,4\},\{3,4\}\big{\}}. $\Omega$ has the closed form

However, if $|\text{supp}\left(\mathbf{w}\right)|=4$, the optimal decomposition is never unique.

This suggests that for a general $\mathcal{G}$, unique solutions are the exception rather than the rule. This motivates a posteriori definitions of group-support that are meaningful in the case where the decomposition is not unique. We consider a necessary and sufficient condition for uniqueness in lemma 48.

Model selection consistency

In this section we consider the estimator $\hat{\mathbf{w}}$ obtained as a solution of the learning problem (13) in the context of a well-specified model. Specifically, we consider the linear regression model:

Several types of consistency results are of interest when using a sparsity-inducing norm as a regularizer. One typically distinguishes classical consistency where $\left\|\hat{\mathbf{w}}-\mathbf{w}^{\star}\right\|_{p}$ converges in probability to zero, prediction consistency where $|L(\hat{\mathbf{w}})-L(\mathbf{w}^{\star})|$ converges to zero in probability, and model selection consistency or support recovery where the support of $\hat{\mathbf{w}}$ coincides with the support of $\mathbf{w}^{\star}$ with high probability. We are interested in the discussion of the last type of result, support recovery, for solutions of (25).

As compared with the Lasso and the group Lasso in the case of disjoint supports, the discussion of support recovery is complicated by several factors here. First, supports that can be recovered are not exactly the ones that can be expressed as unions of groups in $\mathcal{G}$: as the reader might expect, the appropriate notion of support is $J_{1}(\mathbf{w}^{\star})$ (or $\breve{J}_{1}(\mathbf{w}^{\star})$), the one induced by the concept of group-support introduced in section 5. Second, by contrast with the situation of the group Lasso with disjoint groups, the identification of the support $J_{1}(\mathbf{w}^{\star})$ (or $\breve{J}_{1}(\mathbf{w}^{\star})$) is not equivalent to the identification of the group-support $\mathcal{G}_{1}(\mathbf{w}^{\star})$ (or $\breve{\mathcal{G}}_{1}(\mathbf{w}^{\star})$), the latter being now a harder problem. As a consequence one should distinguish support recovery from group-support recovery, and, depending on the context, the appropriate notion to consider for model selection consistency might be one or the other. Third, the group-support is characterized by properties of the set $\mathbf{V}(\hat{\mathbf{w}})$ whose convergence is less trivial to study than that of a vector. For these reasons, we consider only in this paper the classical asymptotic regime in which the model generating the data is of fixed finite dimension $p$ while $n\rightarrow\infty$. However we focus on the harder problem of group-support recovery, which will then imply support recovery results.

The proof of consistency we present below follows a classical proof scheme (Bach, 2008a). However the originality of our work reside in that we characterize the group-support consistency here, which requires in particular to study the convergence of the set-valued map $\mathbf{V}(\hat{\mathbf{w}})$. We therefore start in the next section by introducing appropriate notions of continuity for set-valued functions.

We appeal to the theory of correspondences developed by Claude Berge at the end of the 1950’s (Berge, 1959). In particular, we follow closely its presentation by Border (1985).

A correspondence $\phi$ from a set $X$ to a set $Y$, denoted $\phi:X\twoheadrightarrow Y$, is a set-valued mapping which to each element $x\in X$ associates a set $\phi(x)\subset Y$.

When $X$ and $Y$ are metric spaces, the usual notion of continuity of a function is replaced for correspondences by the following notions:

Given two metric spaces $(X,d)$ and $(Y,\rho)$, a correspondence $\phi:X\twoheadrightarrow Y$ is said to be upper hemicontinuous or u.h.c. (resp. lower hemicontinuous or l.h.c.) if for any point $x\in X$ and any open set $U\subset Y$ such that $\phi(x)\subset U$ (resp. $\phi(x)\cap U\neq\varnothing$) there exists a neighborhood $V$ of $x$ such that, for all $x^{\prime}\in V$, $\phi(x^{\prime})\subset U$ (resp. $\phi(x^{\prime})\cap U\neq\varnothing$). A correspondence is said to be continuous if it is both upper and lower hemicontinuous.

Note that a singleton valued correspondence $\phi$ can be identified with the function $f$ taking this unique value, and that $f$ is continuous if and only if $\phi$ is lower or upper hemicontinuous, both notions being equivalent in that case. The following results, which we prove in appendix A, are key to study the consistency of our method in the next section.

$\mathbf{w}\mapsto\mathcal{A}(\mathbf{w})$ is an upper hemicontinuous correspondence.

2 Group-support recovery

In this section, we state and prove our main consistency results for group-support and support recovery in the least-square linear regression framework (24). We consider two main hypotheses:

We denote $\mathcal{G}_{2}(\mathbf{w}^{\star})\overset{\,\Delta}{=}\mathcal{G}\backslash\mathcal{G}_{1}(\mathbf{w}^{\star})$ and $J_{2}(\mathbf{w}^{\star})\overset{\,\Delta}{=}[1,p\,]\backslash J_{1}(\mathbf{w}^{\star})$. For convenience, for any group of covariates $g$ we note $\mathbf{X}_{g}$ the $n\times\left|\,g\,\right|$ design matrix restricted to the covariates in $g$, and for any two groups $g,g^{\prime}$ we note $\boldsymbol{\Sigma}_{gg^{\prime}}=\frac{1}{n}\mathbf{X}_{g}^{\top}\mathbf{X}_{g^{\prime}}$.

Consider the following two conditions, where we denote $J_{1}(\mathbf{w}^{\star})$ simply by $J_{1}$ for sake of clarity:

Under assumption (H1), for $\lambda_{n}\rightarrow 0$ and $\lambda_{n}n^{1/2}\rightarrow\infty$, conditions (C1) and (C2) are respectively necessary and sufficient for the strong group-support of the solution of (13), $\breve{\mathcal{G}}_{1}(\hat{\mathbf{w}})$ to satisfy with probability tending to $1$ as $n\rightarrow+\infty$:

To show that $\mathbf{w}$ is a feasible solution to (25) it is enough to show that $\forall g\in\mathcal{G}_{2}(\mathbf{w}^{\star}),\>\left\|\nabla_{\!g}L(\mathbf{w})\right\|\leq\lambda_{n}\,d_{g}$. But since the noise has bounded variance,

is $\sqrt{n}$-consistent, and by the union bound we get $\mathcal{P}(\forall g\in\mathcal{G}_{2}(\mathbf{w}^{\star}),\left\|\nabla_{\!g}L(\mathbf{w})\right\|\leq\lambda_{n}\,d_{g})\geq 1-\sum_{g\in\mathcal{G}_{2}(\mathbf{w}^{\star})}\mathcal{P}(\left\|\nabla_{\!g}L(\mathbf{w})\right\|>\lambda_{n}\,d_{g})$. We therefore deduce that, for any $g\in\mathcal{G}_{2}(\mathbf{w}^{\star})$,

Since we chose $\lambda$ such that $\lambda_{n}^{-1}n^{-1/2}\rightarrow 0$, we have

This shows that, under (C2), $\mathbf{w}$ is a feasible solution to (25) whose group-support is contained in $\mathcal{G}_{1}(\mathbf{w}^{\star})$, i.e., we have shown $\breve{\mathcal{G}}_{1}(\hat{\mathbf{w}})\subset\mathcal{G}_{1}(\mathbf{w}^{\star})$.

For the necessary condition, by contradiction, consider a solution supported on $J_{1}$. Then, reusing the previous argument we have

which shows that for the optimality conditions of Lemma 11(b) to hold, condition (C1) is necessary. The previous theorem shows some partial consistency result in the sense that it guarantees that no group outside of the group-support will be selected. Since $\hat{\mathbf{w}}$ also converges with high probability in Euclidean norm to $\mathbf{w}^{\star}$, this implies for the support that with high probability

However, the theorem does not guarantee that all groups in $\breve{\mathcal{G}}_{1}(\mathbf{w}^{\star})$ will be selected. This is not a shortcoming of the theorem: we provide an example in Appendix B which shows that it is possible that $\breve{\mathcal{G}}_{1}(\hat{\mathbf{w}})\subsetneq\breve{\mathcal{G}}_{1}(\mathbf{w}^{\star})$ with probability 1. Nonetheless, we also show in the same appendix that with high probability there exists $\bar{\mathbf{v}}^{\star}\in\mathbf{V}(\mathbf{w}^{\star})$ whose group-support is included in $\breve{\mathcal{G}}_{1}(\hat{\mathbf{w}})$.

With assumptions (H1,H2) and for $\lambda_{n}\rightarrow 0$ and $\lambda_{n}n^{1/2}\rightarrow\infty$, condition (C1) is sufficient for the strong group-support of the solution of (25), $\breve{\mathcal{G}}_{1}(\hat{\mathbf{w}})$, to satisfy with high probability:

Proof The previous theorem shows that (C1) implies, with high probability, $\breve{\mathcal{G}}_{1}(\hat{\mathbf{w}})\subset\mathcal{G}_{1}(\mathbf{w}^{\star})$. However, by Lemma 22, we have that hypothesis (H2) guarantees that $\mathbf{w}\mapsto\mathbf{V}(\mathbf{w})$ is continuous at $\mathbf{w}^{\star}$ for $\mathbf{w}$ with $\text{supp}\left(\mathbf{w}\right)\subset J_{1}(\mathbf{w}^{\star})$. Combined with the fact that $\hat{\mathbf{w}}$ converges in probability with $\mathbf{w}^{\star}$, this implies that $\forall\epsilon>0,\exists n_{0},\forall n>n_{0}$, with probability larger than $1-\epsilon$, $\forall\bar{\mathbf{v}}^{\star}\in\mathbf{V}(\mathbf{w}^{\star})$, there exists $\mathbf{\bar{v}}\in\mathbf{V}(\hat{\mathbf{w}})$ such that $\left\|\mathbf{\bar{v}}-\bar{\mathbf{v}}^{\star}\right\|<\epsilon$. For each $g\in\breve{\mathcal{G}}_{1}(\mathbf{w}^{\star})$, for $\bar{\mathbf{v}}^{\star}\in\mathbf{V}(\mathbf{w}^{\star})$ such that ${\mathbf{v}^{\star}}^{g}\neq 0$, there thus exists $\epsilon>0$ such that the previous convergence results implies that $g\in\breve{\mathcal{G}}_{1}(\hat{\mathbf{w}})$ with high probability. Finally, since $|\breve{\mathcal{G}}_{1}(\mathbf{w}^{\star})|$ is finite, for $n$ large enough, the union bound ensures that, with high probability, $\breve{\mathcal{G}}_{1}(\mathbf{w}^{\star})\subset\breve{\mathcal{G}}_{1}(\hat{\mathbf{w}})$.

The previous theorem shows the best result possible for the situation where $\breve{\mathcal{G}}_{1}(\mathbf{w}^{\star})\neq\mathcal{G}_{1}(\mathbf{w}^{\star})$, as, in the example of the cycle of length 3 of section 6.2, the case of $\mathbf{w}^{\star}=(2,1,1)$. If $\breve{\mathcal{G}}_{1}(\mathbf{w}^{\star})=\mathcal{G}_{1}(\mathbf{w}^{\star})$, then we have the obvious corollary:

With assumptions (H1,H2), and assuming $\breve{\mathcal{G}}_{1}(\mathbf{w}^{\star})=\mathcal{G}_{1}(\mathbf{w}^{\star})$, for $\lambda_{n}\rightarrow 0$ and $\lambda_{n}n^{1/2}\rightarrow\infty$, conditions (C1) and (C2) are respectively necessary and sufficient for the solution of (13) to estimate consistently the correct group-support $\mathcal{G}_{1}(\mathbf{w}^{\star})$.

Remarks: For the Lasso and the usual group Lasso with disjoint groups, the most favorable case w.r.t. to condition (C2) is the case where the empirical covariance of the design is the identity (the same analysis can be done in the random design case), i.e., the case where there is no correlations between groups. In that case, we have $\boldsymbol{\Sigma}_{J_{2}J_{1}}\boldsymbol{\Sigma}_{J_{1}J_{1}}^{-1}=0$ and the mutual incoherence condition is 0. However, in the case of overlap, for $g\in\mathcal{G}$ such that $g\cap J_{1}\neq\emptyset$, then $\boldsymbol{\Sigma}_{gJ_{1}}\boldsymbol{\Sigma}_{J_{1}J_{1}}^{-1}\neq 0$ and we have $\left\|\boldsymbol{\Sigma}_{gJ_{1}}\boldsymbol{\Sigma}_{J_{1}J_{1}}^{-1}\boldsymbol{\alpha}_{J_{1}}\right\|=\left\|\boldsymbol{\alpha}_{g\cap J_{1}}\right\|$. First, this gives yet another motivation to consider the weak-group support, since those groups in the weak-group support are exactly the ones for which $\left\|\boldsymbol{\alpha}_{g\cap J_{1}}\right\|=1$ (see Lemma 14). Second this show that if $g_{1}\in\breve{\mathcal{G}}_{1}(\mathbf{w}^{\star})$ and $g_{2}\notin\mathcal{G}_{1}(\mathbf{w}^{\star})$ have a large overlap then $\left\|\boldsymbol{\alpha}_{g_{1}\cap g_{2}}\right\|$ can be fairly close to $1$ even for a design with identity covariance. This means that it might be very difficult in practice to identify $g_{2}$ correctly as being outside of the support unless large amounts of data are available.

3 Related theoretical results

Maurer and Pontil (2011) give a bound on the Rademacher complexity of linear functions whose parameter vector lies in the unit ball of the norm $\Omega_{\cup}^{\mathcal{G}}$, hence bounding the generalization error of such function. They consider as well extensions of this norm where each of the latent variables in the latent group Lasso are penalized by the norm of their image by some operator.

Our paper and these two papers have thus considered complementary aspects of estimation and recovery in statistical and compressed sensing based on $\Omega_{\cup}^{\mathcal{G}}$ settings which should all contribute to understanding the high-dimensional learning setting.

Choice of the weights

The choice of the weights $d_{g}$ associated to each group has been discussed in the literature on the classical group Lasso, when groups do not overlap. The main motivation for the introduction of these weights is to take into account the discrepancies of size existing between different groups. Yuan and Lin (2006) used $d_{g}=\sqrt{|g|}$, which yields solutions similar to the ANOVA test under a certain design. Bach et al. (2004) in the context of multiple kernel learning used $d_{g}\propto\sqrt{\text{tr}K_{g}}$, where $\{K_{g}\}_{g\in\mathcal{G}}$ are positive definite kernels, with $K_{g}=\mathbf{X}_{g}\mathbf{X}_{g}^{\top}$ in our context; for normalized features such as $\mathbf{X}\mathbf{X}^{\top}=I$, this yields $d_{g}=\sqrt{|g|}$ as well.

In the context of our latent group Lasso with overlapping groups, the choice of the weights is significantly more important than in the case of disjoint groups, and, arguably, than in the case of other formulations considering overlapping groups: indeed, the notions of group-support $\mathcal{G}_{1}(\mathbf{w})$ and $\breve{\mathcal{G}}_{1}(\mathbf{w})$ and of support $J_{1}(\mathbf{w})$ and $\breve{J}_{1}(\mathbf{w})$ associated to a vector $\mathbf{w}$ through the norm $\Omega(\mathbf{w})$ themselves change according to the choice of the weights.

In this section we propose two types of arguments to study the effect of and guide the choice of weights:

On the one hand we consider a vector $\mathbf{w}$ and ask, independently of a learning problem, which groups participate in its group support: there is no point in introducing a group in $\mathcal{G}$ if the weights are such that it can never be included in the group support. We show in Section 8.1 that, for all groups to be useful, weights should increase with the size of the groups, but not too quickly; in Section 8.2 we attempt to characterize when large groups are preferred over unions of smaller ones.

On the other hand, we consider in Section 8.3 a simple regression scenario, and discuss the impact of the weights on the probability to correctly identify relevant groups, and simultaneously control the rate of false positives.

Informally, we are concerned in this section with the fact that, if a group $g$ contains a group $h$ and ${d_{g}}/{d_{h}}$ is too small, $h$ will never enter the group support, and, conversely, if $g$ is covered by a certain number of groups and $d_{g}$ is too large, then $g$ will never enter the group-support.

Formally, we say that a group $g\in\mathcal{G}$ is redundant for a certain set of weights $(d_{g})_{g\in\mathcal{G}}$ if it can be removed without changing the value of the norm $\Omega$ for any $\mathbf{w}$; this is equivalent to asking that the dual norm $\Omega^{*}$ is unchanged.

We first show that if there exists another group $g^{\prime}\in\mathcal{G}$ such that $g\subset g^{\prime}$, $g$ is redundant unless we require that $d_{g}<d_{g}^{\prime}$:

If $g,g^{\prime}\in\mathcal{G}$ satisfy $g\subset g^{\prime}$ and $d_{g}\geq d_{g^{\prime}}$, then for any $\mathbf{w}$, $(g\in\mathcal{G}_{1}(\mathbf{w}))\Rightarrow(g^{\prime}\in\mathcal{G}_{1}(\mathbf{w}))$.

Proof If $d_{g}\geq d_{g^{\prime}}$, and if $g\in\mathcal{G}_{1}(\mathbf{w})$ then $1=\frac{\left\|\boldsymbol{\alpha}_{g}(\mathbf{w})\right\|}{d_{g}}\leq\frac{\left\|\boldsymbol{\alpha}_{g^{\prime}}(\mathbf{w})\right\|}{d_{g^{\prime}}}$, which implies $g^{\prime}\in\mathcal{G}_{1}(\mathbf{w})$.

It would be very natural to try and require that the weights are chosen so that, if $g=\text{supp}\left(\mathbf{w}\right)$, its group-support is exactly $g$. Unfortunately, this is in general not possible: we show a negative result, which arises as a consequence of the previous lemma.

For some group sets $\mathcal{G}$, it is impossible to choose the weights $d_{g}$ independently of $\mathbf{w}$ so that $J_{1}(\mathbf{w})=\text{supp}\left(\mathbf{w}\right)$ (or $\breve{J}_{1}(\mathbf{w})=\text{supp}\left(\mathbf{w}\right)$) if the latter is a union of groups.

Proof Consider the groups $A=\{1,2,3\}$, $B=\{3,4\},C=\{2,3,4\}$ :

To have that $\breve{J}_{1}(\mathbf{w})=\text{supp}\left(\mathbf{w}\right)$ for all $\mathbf{w}$ Lemma 26 imposes that $d_{B}<d_{C}$ so that $B$ is not redundant; this is necessary to have $\breve{J}_{1}(\mathbf{w})=\text{supp}\left(\mathbf{w}\right)=B$ for $\mathbf{w}=(0,0,w,w)$.

Then consider $\mathbf{w}=(0,w,\epsilon,\epsilon)$. $\breve{J}_{1}(\mathbf{w})=\text{supp}\left(\mathbf{w}\right)$ requires that $\breve{\mathcal{G}}_{1}(\mathbf{w})=\{C\}$. But then $\mathbf{v}^{C}=\mathbf{w}$ so that $\boldsymbol{\alpha}=d_{C}\,\mathbf{w}/\|\mathbf{w}\|$. In particular $\|\boldsymbol{\alpha}_{A}\|^{2}=d_{C}^{2}\,(w^{2}+\epsilon^{2})/(w^{2}+2\epsilon^{2})$ and $\|\boldsymbol{\alpha}_{B}\|^{2}=d_{C}^{2}\,2\epsilon^{2}/(w^{2}+2\epsilon^{2})$. For the inequality $\|\boldsymbol{\alpha}_{A}\|\leq d_{A}$ to hold for all $\epsilon>0$, we need $d_{A}\geq d_{C}$.

Finally consider $\mathbf{w}=(\epsilon,\epsilon,w,0)$. Following the same line as for the previous case, $\breve{J}_{1}(\mathbf{w})=\text{supp}\left(\mathbf{w}\right)$ requires that $\breve{\mathcal{G}}_{1}(\mathbf{w})=\{A\}$, which implies that $\mathbf{v}^{A}=\mathbf{w}$ so that $\boldsymbol{\alpha}=d_{A}\,\mathbf{w}/\|\mathbf{w}\|$. In particular $\|\alpha_{B}\|^{2}=d_{A}^{2}\,w^{2}/(w^{2}+2\epsilon^{2})$ and $\|\boldsymbol{\alpha}_{C}\|^{2}=d_{A}^{2}\,(w^{2}+\epsilon^{2})/(w^{2}+2\epsilon^{2})$. For the inequalities, $\|\boldsymbol{\alpha}_{B}\|\leq d_{B}$ and $\|\boldsymbol{\alpha}_{C}\|\leq d_{C}$ to hold for all $\epsilon>0$, we need to have $d_{A}\leq d_{B}$.

These three inequalities are clearly incompatible and $\breve{J}_{1}(\mathbf{w})\subset J_{1}(\mathbf{w})$ which proves the result.

We now characterize more technically redundancy. The intuition behind the next lemma is the following geometric interpretation of the dual norm: the definition of $\Omega^{*}$ implies that its unit ball is the intersection of cylinders of the form $\{\boldsymbol{\alpha}\mid\|\boldsymbol{\alpha}_{g}\|\leq d_{g}\}$. This means that a group $g$ is redundant if its associated cylinder contains the unit ball of the norm induced by the remaining groups. This can be formally stated as follows:

Let $g\in\mathcal{G}$ and $\mathcal{H}\subset\mathcal{G}$ such that $g$ is covered by groups in $\mathcal{H}$, i.e., $g\subset\cup_{h\in\mathcal{H}}\,h$. Then $g$ is redundant if $\displaystyle d_{g}^{2}>\sum_{h\in\mathcal{H}}d_{h}^{2}.$

In the case where the weights depend only on the cardinality of the $g$, i.e., $d_{g}=d_{k}$ for $|g|=k$, we consider the following condition:

Condition (C) is sufficient to guarantee that no group is redundant.

We would like insist that condition (C) is sufficient to guarantee non-redundancy but might be unnecessary for many restricted families of groups, for example as soon as each group contains an element which belongs to no other group. However, without any condition on the set of groups, the previous condition is the weakest possible if the weights depend only on the group sizes, since it becomes necessary in the following special case:

Assume that group $g$ with cardinality $|g|=k$ contains all $k$ groups of size $k-1$, then (C) is necessary for $g$ to be non-redundant.

2 Dominating group

Let us first formalize the notion of group domination.

Let $g\in\mathcal{G}$ and $\mathcal{H}\subset\mathcal{G}$ a set of subgroups satisfying $\forall h\in\mathcal{H},h\subset g$. We say that $g$ dominates $\mathcal{H}$ if $\mathcal{H}$ could be the weak group-support for some $\mathbf{w}$ if $g$ was removed from $\mathcal{G}$, but is the weak group support of no $\mathbf{w}$ in the presence of $g$.

We can characterize the presence of domination in terms of weights as follows:

A group $g$ dominates a set of subgroups $\mathcal{H}$ if and only if, on the one hand, $\mathcal{H}$ is a possible group-support when $g$ is removed from $\mathcal{G}$, and, on the other,

As discussed previously, one natural property to require would be that if $\mathbf{w}$ is exactly supported by a group $g$, its group-support should be $g$. As argued in Lemma 27, we can not have this property in general. We can however show that if the support of $\mathbf{w}$ is a single group in $\mathcal{G}$, then this group is always in the group support of $\mathbf{w}$.

The following result shows that, under some conditions on the weights, we can ensure that a group $g$ does not dominate any set of subgroups that do not cover it entirely.

Let a group $g\in\mathcal{G}$ and a set of subgroups $\mathcal{H}\subset\mathcal{G}$ such that $\forall h\in\mathcal{H},h\subset g$ and $\cup_{h\in\mathbf{h}}h\subsetneq g$. Assuming that $\mathcal{H}$ could be in the group support of some $\mathbf{w}$ if $g$ was removed from $\mathcal{G}$, then $g$ does not dominate $\mathcal{H}$ if, for some constant $d_{1}>0$, weights satisfy $d_{h}\leq\sqrt{|h|}d_{1}$ for all $h\in\mathcal{H}$ and $d_{g}\geq\sqrt{|g|-1}\,d_{1}$.

Proof By Lemma 33, $g$ does not dominate $\mathcal{H}$ if and only if $d_{g}\geq P(g,\mathcal{H})$. To prove this, let us rewrite $P(g,\mathcal{H})$ as the solution of the following optimization problem:

By strong duality of linear programs $P(g,\mathcal{H})$ is also the solution of the dual problem:

But if $\bar{h}\overset{\,\Delta}{=}\cup_{h\in\mathcal{H}}\,h$, under the conditions on the weights in Lemma 34, we can upper bound the optimal value as follows:

where the second inequality results from the constraints of the dual program and the fact that for $i\in g\backslash\bar{h}$, the corresponding terms in the sum are equal to . This shows that if $d_{g}^{2}\geq(|g|-1)\,d_{1}^{2}$, then $d_{g}\geq P(g,\mathcal{H})$. Note that Lemma 33 is tight in the following case:

For any group $g\in\mathcal{G}$, if $\mathcal{H}$ is a set of $|g|-1$ singletons of $g$, each with weight $d_{1}$, that could be in a group support if $g$ was removed, then $g$ dominates $\mathcal{H}$ if and only if $d_{g}<d_{1}\sqrt{|g|-1}$.

Proof This is a direct consequence of Lemma 33, where the value of $P(g,\mathcal{H})$ is trivially equal to $d_{1}\sqrt{|g|-1}$.

What the two previous lemmata indicate is that, if there are large gaps in size between a group of size $k$ and many much smaller subgroups contained in it, it is necessary to choose a value for the weight which is possibly unreasonably large, to allow all combinations of subgroups to be selected (even non-covering ones). Lemma 35 is illustrated on Figure 4, with the the group $\mathcal{G}=\{\{1\},\{2\},\{3\},\{1,2,3\}\}$. Giving singletons the weight $d_{1}=1$, the critical weight for $g=\left\{1,2,3\right\}$ to dominate or not pairs of singletons is $d_{g}=\sqrt{|g|-1}=\sqrt{2}$. We represent it equivalently as $d_{g}=|g|^{\gamma}$ with $\gamma=\frac{\log(2)}{2\log(3)}$ on Figure 4. This corresponds to the critical value, below which it is not possible to select two singletons only . The trade-off we are facing here is not surprising when the weights are thought to correspond to code lengths. Indeed, in light of the interpretation of the norm $\Omega$ as a relaxation of a block coding penalization, it is clear that allowing groups with quite large weights (i.e., code lengths) increases the expressiveness of the code at the expense of compressibility and reduces the strength of the prior on support, since large weight allows for a greater diversity of supports. Put more simply, there is a trade-off between how coarsely the supports are encoded and how informative the prior on the supports is. The trade-off can also be interpreted as a bias-variance trade-off, where biasing the estimate of the support with a coarser set of patterns reduces the variance in its estimation.

It should be noted that, as an important consequence of domination, the set of possible sparsity patterns (although consisting of unions of sets of $\mathcal{G}$) is in general not stable by union.

3 Importance of weights for support consistency, FDR and FWER control

In this section we consider the following regression setting:

where the design matrix is taken to be the identity and the noise to be Gaussian, bearing in mind that the analysis we propose here could be extended easily to the case of a design satisfying properties such as RIP with noise that could be taken more generally subgaussian. The mapping to the solution of this optimization problem is often called the soft-thresholding operator, shrinkage operator or proximal operator associated with the norm $\Omega$. We denote this mapping $\mathbf{w}\mapsto\text{ST}(\mathbf{w})$. In terms of support recovery and group-support consistency, a reasonable minimal requirement is that for sufficiently large values of the coefficients and for small levels of noise, assuming that the distribution of the noise is absolutely continuous with respect to the Lebesgue measure, the solution to problem (26) should retrieve the correct support, provided the latter can be expressed as a union of groups.

We first show that redundant groups may never be selected by (26).

Take $\mathcal{G}=\left\{g,g^{\prime}\right\}$ with $g\subsetneq g^{\prime}$ and $d_{g}\geq d_{g^{\prime}}$. Then for any $\mathbf{w}$, $g\notin\mathcal{G}_{1}(\hat{\mathbf{w}})$ a.s. where $\hat{\mathbf{w}}=\text{ST}(\mathbf{w})$.

Proof We first note that the optimality condition for (26) is

where $\boldsymbol{\alpha}\in\mathcal{A}(\hat{\mathbf{w}})$. We then reason by contradiction and assume $g\in\mathcal{G}_{1}(\hat{\mathbf{w}})$ so that $\left\|\boldsymbol{\alpha}_{g}(\hat{\mathbf{w}})\right\|=d_{g}$. Then, because $g\subsetneq g^{\prime}$, $\left\|\boldsymbol{\alpha}_{g^{\prime}}(\hat{\mathbf{w}})\right\|^{2}=\left\|\boldsymbol{\alpha}_{g}(\hat{\mathbf{w}})\right\|^{2}+\left\|\boldsymbol{\alpha}_{g^{\prime}\backslash g}\right\|^{2}\leq d_{g^{\prime}}$, which implies $\boldsymbol{\alpha}_{g^{\prime}\backslash g}=0=\mathbf{w}_{g^{\prime}\backslash g}+\epsilon_{g^{\prime}\backslash g}-\hat{\mathbf{w}}_{g^{\prime}\backslash g}$. But $\mathbf{w}_{g^{\prime}\backslash g}+\epsilon_{g^{\prime}\backslash g}\neq\mathbf{0}$ a.s., this implies $\hat{\mathbf{w}}_{g^{\prime}\backslash g}\neq\mathbf{0}$, and therefore that $\mathbf{v}^{g^{\prime}}\neq\mathbf{0}$. But $\mathbf{v}^{g^{\prime}}$ restricted to $g^{\prime}\backslash g$ should then both be equal to $\mathbf{0}$ by optimality condition, and be equal to $\hat{\mathbf{w}}_{g^{\prime}\backslash g}$, which is a contradiction. Lemma 36 should be compared to Lemma 26. While the later one shows that $g$ can not be selected without $g^{\prime}$, Lemma 36 shows that in the regression setting it may simply not be selected a.s. This shows in particular that $d_{g}\geq d_{g^{\prime}}$ can pose a problem of support consistency because it implies that, if the only way to write the support as a union of elements of $\mathcal{G}$ is $\text{supp}\left(\mathbf{w}\right)=g$, the support is a.s. never correctly estimated by solving problem (26).

We now discuss in more details the influence of the weights on the probability to select false positives (Section 8.3.1) and to have false negatives (Section 8.3.2)

Let us consider a group $g\in\mathcal{G}$ of size $|g|=k$ which is outside of the support (i.e. $\mathbf{w}^{*}_{g}=\mathbf{0}$), and such that not other group intersecting it is selected. From the optimality condition (27)we see that $\hat{\mathbf{w}}_{g}=\mathbf{0}$ if and only if $\displaystyle\left\|\epsilon_{g}\right\|^{2}\leq\lambda^{2}d_{k}^{2}.$

If we assume that $\lambda=\sigma$, then setting

is an interesting choice because this is, at second order, the smallest possible rate that ensures that each group has a vanishingly small probability of being selected by chance. Indeed, on the one hand, $\left\|\epsilon_{g}\right\|^{2}\sim\sigma^{2}\chi^{2}_{k}$ so the usual Chernoff bound yields:

3.2 False negatives

These choices for $d_{k}$ allow to control for false positives, but it is interesting as well to ask which groups containing true non-zero elements will be selected, and which ones could be false negatives. For simplicity we assume that $\mathbf{w}^{*}_{i}\in\{0,1\}$ and that the noise is Gaussian as previously. If the fraction of non-zero elements in $\mathbf{w}^{*}_{i}$ is $p$ and one assumes a null model $H_{0}$ under which group $g$ is unrelated to the nonzero pattern of $\mathbf{w}^{*}$ then it is reasonable to model the number of non-zero elements in $g$ as a binomial random variable $\mathcal{B}in(k,p)$ with $k=|g|$. Using again the KKT conditions, if none of the groups intersecting $g$ is selected, we will have $\mathbf{v}_{g}=\mathbf{0}$ if and only if $\left\|\mathbf{w}^{*}_{g}+\epsilon_{g}\right\|^{2}\leq\lambda^{2}d_{k}^{2}$.

If $\lambda^{2}=p+\sigma^{2}$ and if $d_{k}$ is chosen of the previous form $d_{k}=\sqrt{k+c\sqrt{k}}$, then, for an appropriate choice of $c$, namely $c=c^{\prime}\,\frac{\sqrt{p(1-p)+4p\sigma^{2}+2\sigma^{4}}}{p+\sigma^{2}}$, classical Chernoff bounds together with an analysis similar to that of the previous section shows that we have $\left\|\mathbf{w}^{*}_{g}+\epsilon_{g}\right\|^{2}>\lambda^{2}d_{k}^{2}$ with probability decreasing exponentially in $c^{\prime}$. Therefore in this model, groups selected can be interpreted as groups that are “enriched” in non-zero coefficients, where we call a group enriched if the number of non-zero coefficients in that group is significantly larger than for a random group of the same size. To put things differently the false negatives correspond to groups that do not have a significant number of non-zero elements.