The Degrees of Freedom of the Group Lasso

Samuel Vaiter, Charles Deledalle, Gabriel Peyré, Jalal Fadili, Charles DossalarXiv 2012 · DOI · arXiv

Abstract

This paper studies the sensitivity to the observations of the block/group Lasso solution to an overdetermined linear regression model. Such a regularization is known to promote sparsity patterns structured as nonoverlapping groups of coefficients. Our main contribution provides a local parameterization of the solution with respect to the observations. As a byproduct, we give an unbiased estimate of the degrees of freedom of the group Lasso. Among other applications of such results, one can choose in a principled and objective way the regularization parameter of the Lasso through model selection criteria.

Introduction

In linear regression, regularization is a fundamental tool for preventing overfitting and promoting structured sparsity. The Group Lasso is a popular extension of the standard Lasso that encourages entire groups of variables to be zero or non-zero together. While the Group Lasso is widely used in fields like genomics and signal processing, a recurring challenge is choosing the optimal regularization strength (the $\lambda$ parameter).

To select $\lambda$ objectively, researchers rely on the model's Degrees of Freedom (DOF)—a metric representing the "effective" number of parameters the model utilizes. In the standard Lasso, the DOF is simply the count of non-zero coefficients. However, because the Group Lasso employs $\ell_2$ norms on blocks of variables, its geometry is more complex, and its DOF is not a simple integer count. This paper provides a rigorous mathematical derivation for the DOF of the Group Lasso, enabling the use of principled selection criteria such as AIC, BIC, or Stein’s Unbiased Risk Estimate (SURE).

Methodology: Sensitivity and Local Parameterization

The authors derive the DOF through sensitivity analysis, examining how the Group Lasso solution $\beta^*(y)$ fluctuates in response to small changes in the observation vector $y$. The technical approach is built on three pillars:

  1. Local Parameterization: The authors prove that for almost any observation vector $y$, there exists a neighborhood where the "support" (the set of active groups) remains constant.
  2. Implicit Function Theorem: Within these stable neighborhoods, the authors apply the implicit function theorem to the first-order optimality conditions of the Group Lasso. This allows for the calculation of the divergence of the prediction with respect to the data.
  3. Stein’s Lemma: By invoking the SURE framework, the authors establish that the divergence of this weakly differentiable estimator serves as an unbiased estimate of its DOF.

Key Insights: The Geometry of Group Sparsity

A significant theoretical contribution of this work is the proof that the "transition space"—the set of data points where the mapping from data to solution is non-smooth (e.g., when a group is on the verge of being toggled)—has zero Lebesgue measure. This ensures the estimator is differentiable "almost everywhere."

Unlike the standard Lasso, the Group Lasso DOF is highly dependent on the magnitudes of the active groups. The resulting formula involves a block-diagonal operator that accounts for projections orthogonal to the direction of each active group. This reflects the fact that the Group Lasso does not just select variables; it applies a specific form of shrinkage that reduces the effective dimensionality based on signal strength.

Main Results

The primary result is Theorem 2, which provides the general formula for the unbiased estimate of the DOF: $$\hat{df} = \text{tr}(X_I d(y))$$ Where $d(y)$ is the differential of the solution.

For the specific case of Block Soft Thresholding (where the design matrix is the identity), the formula simplifies to a very intuitive form: $$\hat{df} = |J| - \lambda \sum_{b \in J} \frac{|b| - 1}{\|y_b\|}$$ In this equation:

  • $|J|$ is the total number of active variables.
  • $|b|$ is the size of group $b$.
  • $\|y_b\|$ is the norm of the observed data for that group.

This reveals that as the signal $(\|y_b\|)$ becomes stronger, the DOF approaches the total number of active variables. However, for weaker signals, the effective parameter count is lower, reflecting the heavier regularization applied to those groups.

Scope and Limitations

While this paper provides a definitive mathematical foundation for Group Lasso complexity, it notes several constraints:

  • Overdetermined Systems: The proofs assume the design matrix $X$ has full column rank ($Q > N$). In high-dimensional (underdetermined) settings, while the prediction is unique, the coefficients themselves might not be.
  • Non-overlapping Groups: The theory is currently limited to disjoint groups. Extending this to the "Overlapping Group Lasso" would require handling more complex dependencies between penalty terms.
  • Computational Cost: For very large-scale applications, calculating the closed-form DOF involves inverting matrices related to the active support, which may be computationally intensive.

Summary updated

Abstract

This paper studies the sensitivity to the observations of the block/group\nLasso solution to an overdetermined linear regression model. Such a\nregularization is known to promote sparsity patterns structured as\nnonoverlapping groups of coefficients. Our main contribution provides a local\nparameterization of the solution with respect to the observations. As a\nbyproduct, we give an unbiased estimate of the degrees of freedom of the group\nLasso. Among other applications of such results, one can choose in a principled\nand objective way the regularization parameter of the Lasso through model\nselection criteria.\n
BibTeX
@misc{vaiter2012degrees,
  author = {Samuel Vaiter and Charles Deledalle and Gabriel Peyré and Jalal Fadili and Charles Dossal},
  title = {{The Degrees of Freedom of the Group Lasso}},
  year = {2012},
  eprint = {1205.1481},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1205.1481},
}
Figure