Source-linked AI summary
A note on the group lasso and a sparse group lasso
J. Friedman, T. Hastie, R. Tibshirani
TL;DR
The paper addresses the group lasso’s inability to produce within-group sparsity and the orthonormality assumption in its standard algorithm. It proposes a convex sparse group-lasso criterion optimized by coordinate descent, yielding sparsity at group and individual-feature levels and handling non-orthonormal group matrices.
Problem
The group lasso cannot select individual features within a nonzero group, while its standard fitting algorithm assumes orthonormal model matrices within groups.
Method
The paper blends lasso and group-lasso penalties in a convex criterion and optimizes it using coordinate descent.
Results
The resulting algorithm also provides an effective method for the group lasso with non-orthogonal model matrices, while the sparse group lasso yields sparsity at both group and individual-feature levels.
Takeaways & Limitations
The sparse group lasso offers a compromise between lasso and group lasso by selecting both groups and individual predictors within groups.
Takeaways & Limitations
Orthonormalizing non-orthonormal predictors generally fails to preserve the original group-lasso penalty, except when the transformation satisfies D = I.
Abstract
from arXiv · showhide
We consider the group lasso penalty for the linear model. We note that the standard algorithm for solving the problem assumes that the model matrices in each group are orthonormal. Here we consider a more general penalty that blends the lasso (L1) with the group lasso ("two-norm"). This penalty yields solutions that are sparse at both the group and individual feature levels. We derive an efficient algorithm for the resulting convex problem based on coordinate descent. This algorithm can also be used to solve the general form of the group lasso, with non-orthonormal model matrices.
1 Introduction
The group lasso selects or excludes entire predictor groups but cannot select individual features within a retained group. The sparse group lasso blends group-level and individual-level sparsity in a convex criterion.
- 1 Introduction: The group lasso applies an Euclidean-norm penalty that can remove an entire predictor group from the model.When all group sizes equal one, it reduces to the lasso.
- 1 Introduction: The group lasso does not produce sparsity within a nonzero group, so all predictors in that group remain nonzero.
- 1 Introduction: The sparse group lasso combines lasso and group-lasso penalties to select groups and individual predictors within groups.Its criterion is convex because it sums convex functions.
- 1 Introduction: The criterion reduces to the group lasso when λ2 = 0.
2 Computation for the group lasso
The standard group-lasso algorithm relies on orthonormal predictors within each group, but orthonormalization can change the penalized coefficient norm. The paper therefore motivates a coordinate-descent approach that handles non-orthonormal model matrices.
- 2 Computation for the group lasso: The reviewed group-lasso algorithm is a blockwise coordinate-descent procedure that cycles through predictor groups under an orthonormality assumption.
- 2 Computation for the group lasso: Orthonormalizing a non-orthonormal group preserves fitted values but generally does not preserve the original group-lasso penalty.The transformed coefficient norm equals the original norm only when D = I.
- 2 Computation for the group lasso: For dummy-variable predictors, the coefficient norms are preserved under this transformation only when category observation counts are equal.
- 2 Computation for the group lasso: The alternative scalar-equation approach for non-orthonormal predictors can be numerically unstable near zero and is not guaranteed to converge.
3 Computation for the sparse group lasso
The sparse group lasso criterion is optimized by block coordinate descent over groups and coordinate descent within each group. With modifications, the same algorithm handles the standard group lasso with non-orthonormal model matrices.
- Block coordinate descent applies because the criterion is separable, allowing optimization to focus on one group at a time.
- Within a group, coordinate descent minimizes a convex differentiable loss plus a separable penalty to obtain the global minimum.
- The algorithm cycles through groups, checks whether a group should be zero, updates individual coefficients, and iterates until convergence.
- When λ2 is zero, the group-level test changes and the individual soft-thresholding check is unnecessary.
- With these modifications, the algorithm effectively solves the group lasso when model matrices are non-orthogonal.
- In the orthonormal special case, the procedure reduces to the algorithm of Yuan and Lin (2007).
4 An example
A simulated example compares lasso, group lasso, and sparse group lasso coefficient selection. The sparse group lasso strikes an effective compromise, producing sparsity at both group and individual predictor levels.
- The simulation used 200 observations and 100 predictors arranged in ten blocks of ten.
- Predictors had correlation 0.2 within groups and zero correlation otherwise, with Gaussian noise of standard deviation 4.0.
- The sparse group lasso struck an effective compromise between lasso and group lasso in the simulated comparison.
- The method yielded sparsity at both the group and individual predictor levels.
Group lasso
The figures visualize coefficient-sign recovery and selection errors in the simulated example. They distinguish errors at the group level from errors among individual features.
- Figure 2 compares true coefficient values with the signs of estimated coefficients from each method.
- Figure 3’s top panel counts misclassified groups as the regularization parameter varies.
- Figure 3’s bottom panel counts individual coefficients misclassified as zero or nonzero relative to their true values.