Group Lasso with Overlaps: the Latent Group Lasso approach

Guillaume Obozinski; Laurent Jacob; Jean-Philippe Vert

Source-linked AI summary

Group Lasso with Overlaps: the Latent Group Lasso approach

Guillaume Obozinski, Laurent Jacob, Jean-Philippe Vert

arXiv:1110.0413v1Oct 3, 2011stat.MLcs.LG

TL;DR

The paper asks how to impose structured sparsity when desired supports are unions of predefined overlapping groups rather than ordinary sparse sets. It introduces latent group Lasso through latent group-supported variables, analyzes its norm and recovery conditions, and reports promising results on simulated and breast cancer data while emphasizing the importance and limits of weight selection.

Problem
The ℓ1 penalty does not encode predefined covariate structure, while overlapping group Lasso does not directly ensure selection of whole groups.
Method
The latent group Lasso applies the usual group Lasso penalty to latent variables supported on overlapping groups and combines them linearly into the parameter vector.
Results
The paper gives sufficient and necessary conditions for group-support recovery and reports promising empirical results on simulated and real data.
Takeaways & Limitations
Latent group Lasso provides a framework for sparse models whose supports are unions of predefined groups, including connected groups in covariate graphs.
Takeaways & Limitations
Weight-selection guidance is heuristic and may require finer analyses under high-dimensional scaling and for specific group collections.

Abstract

from arXiv · show

We study a norm for structured sparsity which leads to sparse linear predictors whose supports are unions of prede ned overlapping groups of variables. We call the obtained formulation latent group Lasso, since it is based on applying the usual group Lasso penalty on a set of latent variables. A detailed analysis of the norm and its properties is presented and we characterize conditions under which the set of groups associated with latent variables are correctly identi ed. We motivate and discuss the delicate choice of weights associated to each group, and illustrate this approach on simulated data and on the problem of breast cancer prognosis from gene expression data.

1. Introduction

The paper develops latent group Lasso to encode structured sparsity with overlapping groups, yielding supports that are unions of predefined groups. It analyzes recovery conditions, weighting choices, and empirical behavior in synthetic and breast cancer prognosis data.

1. Introduction: It addresses the limitation that the ℓ1 penalty does not encode prior structure, while classical group Lasso assumes groups form a partition.Structured sparsity incorporates predefined relationships among covariates selected jointly.
1. Introduction: The latent group Lasso applies a group penalty to latent variables supported on overlapping groups, whose linear combination forms the estimated parameter vector.This construction targets supports that are unions of groups rather than intersections.
1. Introduction: The paper defines group-support as the set of non-zero latent variables and studies its recovery, which is stronger than ordinary support recovery.Group-support recovery typically implies support recovery when the parameter support is exactly a union of groups.
1. Introduction: Weights are especially consequential with overlapping groups because they determine recoverable supports and the complexity of possible models.The paper discusses this weighting choice as a central issue.
1. Introduction: Under appropriate conditions, the regularized linear-regression estimators are consistent for sufficiently sparse group-supports in a classical asymptotic setting.The result is established using correspondence theory.
1. Introduction: Experiments on simulated data and breast cancer gene-expression data evaluate support recovery, estimation error, weighting effects, and biologically informed group constructions.The real-data application uses biological pathways and gene networks as prior information.

2. Notations

This section establishes notation for vectors, supports, groups, overlaps, projections, and latent-variable decompositions used throughout the paper. It also fixes the group collection and its coverage assumptions.

2. Notations: The ℓq norm is defined for q ≥ 1, with ∥w∥ denoting the Euclidean norm and supp(w) denoting the nonzero covariates.These definitions provide the basic vector and support notation.
2. Notations: A group is a subset of [1,p], and two groups overlap when they share at least one covariate.The complement and projection onto a group are also defined.
2. Notations: G denotes the fixed collection of groups, with m = |G|, and every covariate is required to belong to at least one group.This coverage condition supports the subsequent group-based constructions.
2. Notations: V_G is the set of group-indexed vector tuples whose component v_g is supported inside its corresponding group g.This notation represents group-constrained latent components.
2. Notations: For differentiable functions, ∇f(w) denotes the gradient and ∇_g f(w) the partial gradient over covariates in group g.These gradients are used in optimization arguments.

3. Group Lasso with overlapping groups

Standard group Lasso behaves undesirably with overlapping groups because zeroing one group also zeroes shared variables. The latent formulation instead decomposes parameters into group-supported latent vectors so selected supports can be unions of overlapping groups.

Motivation: With overlapping groups, standard group Lasso can leave only variables in a remaining group that are absent from the zeroed groups.Its support is therefore generally an intersection-like pattern rather than an entire selected group.
Latent formulation: The latent formulation introduces one vector per group, restricts each vector to its group, and sums the latent vectors to form the parameter.Applying the ℓ1/ℓ2 penalty to latent vectors encourages some group components to vanish while retaining the remaining group-supported components.
Latent formulation: The resulting estimator is designed to have a support that is a union of predefined groups.This differs from the support pattern induced by directly penalizing the parameter with the overlapping-group ℓ1/ℓ2 penalty.
Reformulations: The formulation can be implemented as group Lasso after duplicating covariates that belong to multiple groups.The paper also connects this duplicated-space formulation to nonlinear extensions and multiple kernel learning.
Comparison: When groups form a partition, latent group Lasso and standard group Lasso coincide; with overlaps, their penalties and unit-ball geometries differ.For groups {1,2} and {2,3}, the latent norm has singularities associated with selecting either overlapping group.
Extensions: The choice of positive group weights is especially delicate when groups overlap, and the paper discusses alternative ℓq penalties and related decompositions.These extensions change the induced group-support when the norm or weights change.

4. Some properties of the latent group Lasso penalty

The paper establishes mathematical properties of the latent group Lasso penalty and develops equivalent variational, duplicated-covariate, and multiple-kernel formulations. It also characterizes its geometry through convex-hull and atomic-norm descriptions.

Norm properties: The latent group Lasso penalty is a valid norm with nonempty, compact, and convex sets of optimal decompositions.The paper derives this norm property and analyzes the decomposition set for every parameter vector.
Variational formulations: The norm admits three variational formulations with solution sets denoted V(w), A(w), and Λ(w).These formulations support subsequent analyses of duality, decompositions, and consistency.
Geometry: Its unit ball is the convex hull of group-supported hyper-disks, making the norm an atomic norm associated with their union.This geometric characterization also identifies the norm as the gauge of that convex hull.
Covariate duplication: Regularized empirical-risk minimization with the latent norm is equivalent to regular group Lasso in a space formed by duplicating covariates across overlapping groups.The equivalence provides a practical implementation route and motivates extensions to nonlinear functions.
Multiple kernel learning: The same reformulation yields a multiple kernel learning interpretation that naturally allows overlapping groups.Unlike the original disjoint-group setting, the duplicated representation removes the requirement that the original groups be disjoint.
Nonlinear extensions: Nonlinear kernels can detect group-level relationships that a linear kernel may miss, including nonlinear associations among genes within a group.The paper gives RBF and sequence- or graph-kernel examples as possible extensions.

5. Group-support

Group-support describes which predefined groups participate in an optimal latent decomposition, extending ordinary variable support to overlapping-group structure. The paper distinguishes strong and weak versions and studies their relationship to recovery and dual variables.

Definitions: The group-support of a latent decomposition is the set of groups whose latent vectors are nonzero.For a parameter vector, strong group-support is defined using the union of group-supports across all optimal decompositions.
Definitions: If the optimal decomposition is unique, strong group-support equals the groups with nonzero latent vectors in that decomposition.The paper also defines weak group-support through uniqueness properties of optimal dual variables.
Definitions: Strong group-support is contained in weak group-support; equality defines an unambiguous group-support, while strict containment makes it ambiguous.Thus ambiguity reflects disagreement between the two group-level characterizations.
Dual interpretation: Strong and weak group-support correspond respectively to strongly active and weakly or strongly active dual constraints in a variational formulation.This links decomposition-based support notions to optimality conditions.
Dual interpretation: Variables in the weak and strong group-support sets form J1(w) and ˘J1(w), with ˘J1(w) contained in J1(w).On J1(w), the optimal dual variables are uniquely determined.

6. Illustrative examples

The examples show that overlapping groups can produce non-unique latent decompositions and distinct weak versus strong group-supports. In a three-group cycle, group-support need not be a minimal cover, while larger configurations further motivate definitions that remain meaningful under non-uniqueness.

For p = 3 and groups {{1, 2}, {2, 3}}, the optimal decomposition is unique when (w1, w3) ≠ 0.
When (w1, w3) = 0, every γ ∈ [0, 1] gives an optimal decomposition, but weak and strong group-support coincide.The resulting variable group-support is J1 = ˘J1 = {1, 2, 3}.
Cycle of length 3: With groups {1, 2}, {1, 3}, and {2, 3}, vectors in the interior of Wbal have all three groups in their group-support.Any two groups already cover the variable support, so this group-support is not a minimal cover.
Cycle of length 3: On the boundary of Wbal, weak group-support is ambiguous and contains all three groups, whereas strong group-support matches the adjacent outer region.

7. Model selection consistency

The paper studies recovery of latent group-support in least-squares linear regression, where overlapping groups make the relevant recoverable support more subtle than ordinary variable support. Using correspondence theory within a fixed-dimensional asymptotic regime, it derives conditions for consistent recovery and identifies a limitation caused by large overlaps.

Overlapping groups complicate support recovery because recoverable supports are characterized by weak or strong group-support rather than only unions of predefined groups.The analysis focuses on fixed p as n →∞ and on the harder group-support recovery problem.
The consistency analysis uses convergence of the set-valued map V(ŵ), building on a classical proof scheme and correspondence theory.The paper establishes upper hemicontinuity of A(w) and continuity of V(w + u) under a fixed-support condition.
Under (H1), λn → 0, and λn n^1/2 →∞, conditions (C1) and (C2) are respectively necessary and sufficient for strong group-support recovery with probability tending to 1.
Theorem 24 guarantees that the estimated strong group-support is contained in the true weak group-support under condition (C2).Thus, no group outside the relevant true group-support is selected, although inclusion of every true group is not guaranteed.
If strong and weak group-support coincide for the true parameter, conditions (C1) and (C2) consistently recover the correct group-support.
Large overlaps between an active and inactive group can make the inactive group difficult to identify correctly, even with identity covariance, unless data are plentiful.

8. Choice of the weights

The paper shows that weights in overlapping latent group Lasso determine redundancy, dominance, recoverable supports, and support-consistency behavior. It develops sufficient conditions and interprets weight selection as a trade-off between expressiveness and informative sparsity priors.

Weight effects: Weights are substantially more important with overlapping groups because they change group-support, support, recoverable patterns, and model-class complexity.The paper emphasizes that these effects are stronger than with disjoint groups.
Redundancy: If g ⊂ g′ and d_g ≥ d_g′, selecting g implies selecting g′, while g may never be selected in regression.Thus, when a support can only be represented by g, the estimator may fail to recover that support.
Redundancy: No weights independent of w can always make group-support equal the support for every collection of overlapping groups.This negative result limits universal support-consistency guarantees.
Non-redundancy: Condition (C) is sufficient for non-redundancy, but can be necessary when a group contains all groups of one-smaller size.For restricted group families, the condition may be unnecessary.
Weight scaling: Weights d_k = k^γ interpolate between larger-group and smaller-group preference, with singleton-dominated behavior approaching the ℓ1 norm.For the illustrated groups, intermediate γ values activate all groups in some region, whereas γ = 1/2 removes the largest group from the ball.
Trade-offs: Larger weights increase support expressiveness but reduce compressibility and prior strength, creating a bias–variance trade-off in support estimation.The paper also notes that domination can make possible sparsity patterns unstable under union.

9. Graph Lasso

The graph Lasso setting uses overlapping groups to encourage selected covariates to form connected components, with group construction controlling the scale of selected structures.

The method targets sparse models whose selected covariates form a limited number of connected components in a given graph.
The group collection can consist of edges, cliques, or other subgraphs whose unions generate connected components.
Linear subgraphs of length k control the size of selected connected-variable groups and should usually be slightly smaller than the expected minimal component size.

10. Experiments

Experiments show that overlapping-group penalties improve structured pattern recovery and can reduce prediction error, while weighting strongly affects which supports are selected and how large they are. Gene-expression applications further show gains in predictive performance and network connectivity, with support size and weighting remaining important caveats.

Synthetic data: given overlapping groups: Up to 92% of runs for n = 50 and more than 99% over more than one third of the path for n = 100 selected the correct pattern with the overlapping-group penalty.
Synthetic data: given overlapping groups: The overlapping-group penalty decreases MSE compared with the classical Lasso across a large range of training-set sizes while also improving pattern recovery.
Synthetic data: effect of the weights: Larger groups improve pattern recovery but make exact support boundaries harder to identify because consecutive groups become highly correlated.
Synthetic data: effect of the weights: The weighting scheme significantly influences variable-selection behavior, and the reported tables evaluate MSE, model size, pattern-recovery error, and regularization choices across replications.
Synthetic data: effect of the weights: Weighting controls selection granularity: uniform weights favor the largest groups, whereas intermediate choices can recover the correct support over part of the regularization path.
Synthetic data: effect of the weights: In harder regimes, intermediate weighting can provide better pattern recovery, while with 30 training points and 300 dimensions uniform weights perform best.
Breast cancer data: pathway analysis: In gene-expression experiments, the group penalty consistently improves performance over ℓ1 by 2% to 12% depending on the fold, with the unweighted version outperforming the weighted version tested.
Breast cancer data: pathway analysis: The group penalty selects more genes because it enforces sparsity at the gene-set level rather than the individual-gene level, while weighting further increases the number selected.

11. Conclusion

The paper presents latent group Lasso for sparse models supported on unions of predefined groups and studies group-support recovery. It highlights weight selection and identifies computational, structural, and comparative questions for future work.

Latent group Lasso produces sparse models whose supports are unions of predefined groups, including connected covariates in a graph.
The paper gives sufficient and necessary conditions for recovering the same union of groups as in the penalty-induced decomposition.
Future work includes characterizing efficient computation, encodable structures, and appropriate weights under high-dimensional consistency analyses.
The paper calls for systematic comparisons with other group Lasso formulations, including Jenatton et al.'s approach.

Appendix A. Proofs of Lemmata 21 and 22

This appendix introduces correspondence-theoretic tools used to prove continuity properties of the latent group Lasso’s decomposition-related correspondences. Berge’s maximum theorem provides the central continuity result.

These results establish the technical framework for proving continuity of the correspondences used later in the appendix.
The appendix reviews technical lemmas concerning upper and lower hemicontinuity of correspondences and their compositions and products.
Berge’s maximum theorem states that a continuous objective over a compact-valued continuous correspondence yields a non-empty, compact-valued, upper hemicontinuous argmax correspondence.

A.2 Proof of Lemma 21

The proofs establish upper and lower hemicontinuity for decomposition-related correspondences by combining compactness, uniqueness, matrix representations, and Berge’s maximum theorem.

Berge’s maximum theorem proves upper hemicontinuity of the optimal dual correspondence A(w) because its feasible unit ball is compact-valued and constant.
The optimal-decomposition correspondence V(w) is compact-valued and upper hemicontinuous through an argmin formulation over a compact-valued continuous decomposition correspondence.
When wi ≠ 0, the associated ζi value is locally unique and continuous, supporting lower hemicontinuity arguments for active-group coefficients.
The adjacency matrix and Moore–Penrose pseudoinverse parameterize active-group solutions, while kernel directions describe the remaining solution set.
Perturbations supported on the current support cannot introduce groups outside the current active-group set in a sufficiently small neighborhood.
Combining continuity of dual variables, active-group coefficients, and latent decompositions establishes lower hemicontinuity of V near the reference point.

Appendix B. Partial group-support recovery

This appendix studies partial group-support recovery and shows how recovered group supports relate to optimal decompositions, including cases with non-unique decompositions and explicit low-dimensional formulas.

Hypothesis H1 alone does not provide an inclusion lower bound for recovered group support, suggesting H2 is needed for group-support recovery.
For w⋆ = (1, 0, 0, 0), noise can yield several possible recovered group supports, including the full group set.
The recovered group support contains at least the group support of one decomposition of the true support.
In a three-group configuration, the latent coefficients satisfy λ12 = γ(|w1| + |w2| − |w3|), with analogous expressions for λ13 and λ23.
The three-group solution with all λg > 0 is valid only when no coordinate dominates the sum of the other two.
Outside the balanced region, one latent coefficient is zero and the problem reduces to a case with only two active groups.
Some non-sparse vectors on a cycle admit several optimal decompositions, illustrating non-uniqueness in overlapping-group representations.

C.3 All groups are active

When all four overlapping groups are active, the latent-variable decomposition can be non-unique and is parameterized by a continuous degree of freedom. Boundary choices of that parameter remove individual groups from the group-support.

All groups are active: The shared-variable equations impose |w1|(λ24 + λ34) = |w4|(λ12 + λ13) and |w2|(λ13 + λ34) = |w3|(λ12 + λ24).
All groups are active: The group-incidence system ζ = Bλ can have non-unique solutions because B is singular with kernel span (−1, 1, 1, −1)T.If all λ values are positive, multiple decompositions exist whenever the relevant pre-image intersects the positive orthant.
All groups are active: The feasible solutions are parameterized by ν ∈ [0, 1], with λ12 = νζ1, λ13 = (1 − ν)ζ1, λ24 = ζ2 − νζ1, and λ34 = ω − ζ2 − (1 − ν)ζ1.The parameterization holds under the stated ordering ζ1 ≤ ζ2 ≤ ω − ζ2 ≤ ω − ζ1.
All groups are active: Setting ν = 0 removes group {1, 2}, while setting ν = 1 removes group {1, 3} from the group-support of ¯v.
All groups are active: The decomposition is non-unique in this case, corresponding to the situation characterized by Lemma 48.

Appendix D. Uniqueness of the decomposition

The decomposition is unique exactly when the incidence submatrix restricted to the support and strong group-support has full row rank. Rank deficiency permits alternative positive latent-variable solutions, while full row rank yields strict convexity and a unique optimum.

Uniqueness condition: The decomposition is unique if and only if BJ0 ˘G1 has full row rank.BJ0 ˘G1 uses rows indexed by supp(w) and columns indexed by the strong group-support.
Non-uniqueness: If BJ0 ˘G1 is row-rank deficient, its nontrivial kernel generates multiple latent-variable solutions with the same ζJ0.A neighborhood of kernel perturbations remains feasible because the active λg values are positive.
Uniqueness condition: Full row rank makes the restricted Hessian positive definite, so the objective is strictly convex and the optimum is unique.The proof uses the equivalence between positive semidefiniteness of the transformed Hessian and full row rank of BJ0 ˘G1.