Degrees of Freedom in Penalized Regression: Model Selection with Adaptive Penalties

1. Problem Statement

In penalized regression, model selection relies heavily on accurate assessments of model complexity, typically quantified by the effective degrees of freedom (df).

• The Lasso Benchmark: For the standard Lasso (L1 regularization), it is a well-established result (Zou et al., 2007) that the degrees of freedom equal the size of the active set (the number of non-zero coefficients). This provides a simple, unbiased estimator.
• The Gap: This simplicity is often incorrectly extended to more complex methods, such as the Adaptive Lasso, Group Lasso, and Adaptive Group Lasso. These methods introduce data-dependent weights or group structures that fundamentally alter the relationship between the fitted values and the data.
• The Consequence: Using the active set size as a proxy for degrees of freedom in these adaptive settings leads to biased risk estimation (e.g., AIC/BIC), resulting in suboptimal model selection and unreliable inference. Specifically, the active set size fails to account for the additional complexity introduced by data-driven weighting or the specific shrinkage properties of group norms.

2. Methodology

The authors derive unbiased estimators for the effective degrees of freedom within Stein's Unbiased Risk Estimation (SURE) framework.

• Core Definition: The degrees of freedom are defined as the divergence of the fitted values with respect to the response vector:
  $$\text{df}(\hat{y}) = \mathbb{E}\left[ \text{trace}\left( \frac{\partial \hat{y}}{\partial y} \right) \right]$$
• Analytical Approach: The authors derive closed-form expressions for $\frac{\partial \hat{y}}{\partial y}$ by analyzing the first-order optimality conditions of the penalized objective functions.
• Key Distinction: Unlike the standard Lasso, where the projection matrix remains constant between transition points, adaptive methods involve weights ($w$) that depend on the data ($y$) via preliminary estimates (e.g., OLS). Therefore, the derivative $\frac{\partial \hat{y}}{\partial y}$ must account for the chain rule applied to these data-dependent weights.
• Design Matrices: The analysis covers both orthonormal designs ($X^\top X = I_p$) and general non-orthonormal designs, providing rigorous results for the latter, which are often omitted in existing literature.

3. Key Contributions and Results

A. Adaptive Lasso

The paper derives the first unbiased estimator for the degrees of freedom of the Adaptive Lasso.

• Result: The df is not merely the active set size $|A|$. It includes an additional term reflecting the sensitivity of the adaptive weights to the data.
  • Orthonormal Case: $\widehat{\text{df}}_\gamma = |A| - \gamma \sum_{j \in A} \frac{\partial w_j}{\partial z} \big|_{z=\hat{\beta}^{LS}_j}$.
  • General Case: Includes terms involving the signs of the estimates, the signs of the OLS estimates, and the diagonal elements of the precision matrix of the active set.
• Key Insight: For standard decreasing weights (e.g., $w_j = 1/|\hat{\beta}^{LS}_j|$), the additional term is positive. Thus, $\widehat{\text{df}}_\gamma > |A|$. The common practice of using $|A|$ systematically underestimates the true complexity.
• Behavior: The df is a piecewise linear function of the regularization parameter $\gamma$ (unlike the piecewise constant Lasso). Counter-intuitively, increasing $\gamma$ (stronger regularization) does not always decrease the estimated df immediately due to the non-linear interaction of adaptive weights.

B. Group Lasso

The authors revisit the Group Lasso, providing an alternative derivation that holds for general design matrices.

• Result: The df is given by the trace of a specific matrix involving the design matrix and the group structure:
  $$\widehat{\text{df}}_\gamma = \text{trace}\left[ (I_n + \gamma B)^{-1} A \right]$$
  where $A$ and $B$ depend on the active groups and the geometry of the design.
• Key Insight: Unlike the Adaptive Lasso, the Group Lasso exhibits a deflation effect. The estimated df is strictly lower than the size of the active set ($|A_p|$) and bounded below by the number of active groups ($|A_G|$).
  $$|A_G| \leq \widehat{\text{df}}_\gamma \leq |A_p|$$
  This indicates that the $\ell_2$ group penalty uses information more parsimoniously than the $\ell_1$ penalty.
• Monotonicity: The paper characterizes the monotonicity of the df along the regularization path. While monotonicity holds for orthonormal designs, it is not guaranteed for general designs unless specific spectral conditions on the matrix $\Pi_{AG} + \gamma \frac{d\Pi_{AG}}{d\gamma}$ are met.

C. Adaptive Group Lasso

This method combines the inflation effect of adaptive weights and the contraction effect of the group norm.

• Result: The df estimator incorporates both effects:
  $$\widehat{\text{df}}_\gamma = \text{trace}\left[ (I_n + \gamma B)^{-1} (A - \gamma C) \right]$$
  where $C$ captures the derivative of the adaptive weights.
• Key Insight: The net effect on complexity depends on the relative strength of the inflation (from weights) and contraction (from $\ell_2$ norm). Under standard conditions, the Adaptive Group Lasso df is bounded below by the Group Lasso df.

4. Empirical Assessment

The authors validate their theoretical findings through:

1. Synthetic Data: Simulations with $n=100, p=30$ and grouped variables.
   • Finding: The proposed df estimators are unbiased (matching the covariance formula benchmark).
   • Model Selection: Using the correct df in BIC leads to selecting the true number of variables (9) in the vast majority of cases. In contrast, using the active set size as a proxy leads to over-selection (retaining noise variables) for Group Lasso and under-selection for Adaptive methods.
2. Real Data (Diabetes Dataset):
   • Lasso vs. Adaptive Lasso: The correct df curve is strictly above the active set size. Using the active set size leads to selecting a larger $\gamma$ (over-regularization).
   • Group Lasso vs. Adaptive Group Lasso: The correct df curve is strictly below the active set size. Using the active set size leads to selecting a smaller $\gamma$ (under-regularization).
   • Conclusion: The proposed method yields model selection performance comparable to computationally intensive cross-validation, whereas the naive active-set proxy introduces significant bias.

5. Significance and Implications

• Theoretical Advancement: The paper resolves a long-standing issue in penalized regression by providing rigorous, unbiased df estimators for adaptive and grouped methods under general design conditions. It corrects the misconception that "active set size = degrees of freedom" is a universal rule.
• Practical Impact:
  • Reliable Model Selection: Enables the use of information criteria (AIC/BIC) for Adaptive Lasso and Group Lasso without resorting to expensive cross-validation.
  • Inference: Provides a foundation for valid statistical inference (e.g., confidence intervals, hypothesis testing) in adaptive settings, which previously relied on flawed complexity estimates.
  • High-Dimensional Extension: The authors briefly explore the $n < p$ regime (where OLS is undefined), suggesting ridge regression as a surrogate for weight construction, noting that their df estimators remain superior to the active-set proxy even in this challenging setting.

In summary, this work establishes that data-dependent penalization fundamentally changes model complexity. Ignoring the additional terms induced by adaptive weights or group structures leads to systematic errors in risk estimation and model selection. The derived formulas provide the necessary tools to accurately quantify this complexity.