Source-linked AI summary
The composite absolute penalties family for grouped and hierarchical variable selection
Peng Zhao, Guilherme Rocha, Bin Yu
TL;DR
High-dimensional data require regularized methods, but predictor groupings and hierarchies can provide additional structure for variable selection. The paper introduces CAP penalties and associated algorithms, finding improved predictive performance over LASSO in simulations, including small-n-large-p settings and misspecified groupings.
Problem
High-dimensional variable selection needs regularization, while existing approaches provide limited ways to incorporate known grouping and hierarchical relationships among predictors.
Method
CAP combines norms across groups, using nonoverlapping groups for grouped selection and overlapping patterns for hierarchical selection; BLASSO, cross-validation, and iCAP-based degrees-of-freedom criteria compute and tune estimates.
Results
CAP improved predictive performance over LASSO in simulations, including small-n-large-p settings and groupings ranging from 50% to 150% of the true number of groups.
Takeaways & Limitations
CAP estimates can provide more interpretable, stable, and degrees-of-freedom-parsimonious models while respecting supplied group and hierarchical structure.
Takeaways & Limitations
Degrees-of-freedom results beyond the stated iCAP settings require a way to determine the dimension of a projecting subspace, which remains a future-research problem.
Abstract
from arXiv · showhide
Extracting useful information from high-dimensional data is an important focus of today's statistical research and practice. Penalized loss function minimization has been shown to be effective for this task both theoretically and empirically. With the virtues of both regularization and sparsity, the $L_1$-penalized squared error minimization method Lasso has been popular in regression models and beyond. In this paper, we combine different norms including $L_1$ to form an intelligent penalty in order to add side information to the fitting of a regression or classification model to obtain reasonable estimates. Specifically, we introduce the Composite Absolute Penalties (CAP) family, which allows given grouping and hierarchical relationships between the predictors to be expressed. CAP penalties are built by defining groups and combining the properties of norm penalties at the across-group and within-group levels. Grouped selection occurs for nonoverlapping groups. Hierarchical variable selection is reached by defining groups with particular overlapping patterns. We propose using the BLASSO and cross-validation to compute CAP estimates in general. For a subfamily of CAP estimates involving only the $L_1$ and $L_{\infty}$ norms, we introduce the iCAP algorithm to trace the entire regularization path for the grouped selection problem. Within this subfamily, unbiased estimates of the degrees of freedom (df) are derived so that the regularization parameter is selected without cross-validation. CAP is shown to improve on the predictive performance of the LASSO in a series of simulated experiments, including cases with $p\gg n$ and possibly mis-specified groupings. When the complexity of a model is properly calculated, iCAP is seen to be parsimonious in the experiments.
1. Introduction.
High-dimensional settings make regularized variable selection valuable, while grouping and hierarchy can provide additional structure for stable, interpretable estimates. The paper introduces CAP penalties to encode these relationships and develops computational and model-selection procedures for them.
- Motivation: High-dimensional data often contain far more variables than observations, making parameter estimates overly responsive to noise.Microarray data may contain thousands of gene expressions but only a few hundred samples.
- Motivation: Grouping and hierarchical information can impose further regularization constraints beyond sparsity alone.Examples include dummy variables for categorical predictors and interaction terms that follow corresponding main effects.
- CAP framework: CAP combines norms across defined groups to express grouped selection with nonoverlapping groups and hierarchical selection with particular overlapping patterns.The overlapping structure and norms determine the properties of the resulting estimates.
- CAP framework: CAP extends earlier structured penalties by allowing different norms and overlapping groups, producing computational and modeling gains.The L1 and L∞ combination is computationally convenient, while overlapping groups represent predictor hierarchies.
- Computation and selection: For iCAP penalties under L2-loss, unbiased degrees-of-freedom estimates enable information-criterion selection without cross-validation.The resulting models had predictive performance comparable to cross-validated models even when n ≪p.
- Computation and selection: For general CAP penalties, the authors propose BLASSO to compute regularization paths and cross-validation to select regularization.CAP penalties are convex whenever all norms used in their construction are convex.
- Results: Simulations found that CAP improved predictive performance over LASSO, remained robust to severely misspecified groupings, and used degrees of freedom parsimoniously.The estimates were not sparser by variable count, but were more stable and more parsimonious in degrees of freedom.
2. The Composite Absolute Penalty (CAP) family.
The CAP family combines norm penalties across and within predictor groups to encode grouped or hierarchical selection. Its structure is determined by group overlap and norm choices, with specialized algorithms and selection methods for useful subfamilies.
- Bridge preliminaries: The bridge parameter γ changes coefficient behavior from sparsity at γ ≤ 1 to diagonal concentration when 2 < γ ≤ ∞.For 1 < γ < 2, directions closer to coordinate axes are favored, whereas γ = 2 does not favor a particular direction.
- CAP construction: CAP extends bridge penalties by combining an overall norm with group-specific norms to represent structured relationships among predictors.The overall norm controls relationships across groups, while each group norm controls relationships among coefficients within that group.
- Grouped selection: For γ0 = 1 and γk > 1, variables within each group are selected as a block; nonoverlapping groups produce grouped selection.The group norms act within groups, while sparsity in the across-group norm selects groups.
- Computation and selection: The iCAP family uses L1 and L∞ norms, enabling piecewise-linear regularization paths and fast path-tracing algorithms for grouped and tree-hierarchical selection.The corresponding algorithms are iCAP for nonoverlapping groups and hiCAP for tree hierarchies.
- Model selection and experiments: For iCAP with L2-loss, unbiased degrees-of-freedom estimates allow information criteria to select a model along the path without cross-validation.The paper also reports that simulations provide evidence that adding group structure can greatly enhance predictive performance.
- Hierarchical selection: Overlapping groups can encode hierarchy by arranging groups so later variables appear wherever earlier variables do, while also giving later variables a group of their own.For example, G1 = {1,2} and G2 = {2} induces X1 to enter before X2 under γ0 = 1 and γm > 1.
3. Computing CAP estimates.
CAP estimates are computed through convex optimization and regularization-path algorithms tailored to general penalties, grouped selection, and tree-structured hierarchical selection. For iCAP, path-based degrees-of-freedom estimates support information-criterion selection instead of cross-validation, but broader settings still require further development.
- Convexity: Convex CAP objectives can be solved globally when all construction norms and the loss function are convex.The paper uses KKT conditions to trace solutions across regularization values.
- Specialized path algorithms: For L2-loss with γ0 = 1 and γk ≡∞, iCAP traces grouped-selection paths, while hiCAP handles tree-structured hierarchical selection.iCAP operates at the group level like Lasso and within groups like iLASSO.
- General CAP computation: BLasso approximates regularization paths for general convex losses and CAP penalties using forward and penalty-aware backward steps.Its step size trades computational expense against approximation precision.
- Specialized path algorithms: The iLASSO path preserves KKT conditions between breakpoints and advances until an index moves between active maximum-coefficient and lower-coefficient sets.The grouped iCAP extension similarly tracks changes in active groups and within-group index sets.
- Specialized path algorithms: Hierarchical iCAP forms subtree-based groups and traces paths subject to correlation and coefficient-order constraints among supernodes.Its validity is restricted to tree hierarchies with L2-loss, γ0 = 1, and γk ≡∞.
- Selecting λ: For nonoverlapping-group iCAP under L2-loss, unbiased degrees-of-freedom estimates enable information-criterion selection of λ without cross-validation.The paper uses Sugiura’s AICc and notes that broader L1/L∞ CAP settings still lack a general projecting-subspace dimension calculation.
4. Experimental results.
Simulations evaluated CAP for grouped and hierarchical selection against LASSO, including noisy or misspecified grouping structures. CAP generally improved prediction and structure-aware sparsity, while performance depended on the hierarchy or norm assumptions.
- CAP simulations compared predictive performance, sparsity, parsimony, and tuning-parameter selection against LASSO under grouped and hierarchical structures.The experiments used simulated data, including data-determined groupings and misspecified cluster counts.
- Grouped selection: The L∞ norm made iCAP more sensitive to grouping misspecification, because it relies more heavily on prespecified group information.Other CAP predictive improvements were reported as robust to misspecified group counts.
- Grouped selection: CAP selected more variables but fewer groups than LASSO, reflecting block inclusion and better preservation of the supplied group structure.LASSO often selected only a few variables from each true group, whereas CAP used fewer groups when group selection was the goal.
- Grouped selection: iCAP achieved better or comparable predictive performance to LASSO, with gains especially pronounced for grouped correlated predictors as p/n increased and preserved under misspecified groupings.The results included both Grouped Laplacian and Individual Laplacian settings.
- Hierarchical selection: Hierarchical CAP reduced model error for low and moderate interactions and generally selected no more variables than LASSO, but LASSO performed better for very strong interactions.The strong-interaction case produced comparable CAP and LASSO results before the very-strong-interaction reversal.
- Hierarchical selection: For the multiresolution hierarchy, CAP greatly reduced model error and selected variables while enforcing the hierarchy more closely than LASSO.hiCAP exactly satisfied the hierarchy, whereas small deviations for GLASSO and CAP(4) were attributed to BLASSO approximation.
5. Discussion and concluding remarks.
CAP extends structured regularization by combining norms across overlapping or nonoverlapping predictor groups. Simulations found improved prediction and interpretable structured models, while fully data-driven structure estimation remained future work.
- CAP combines Lγ-norm penalties on defined groups to incorporate predetermined grouping and hierarchical structures among predictors.The group definitions and norm choices determine the properties of the resulting estimates.
- Nonoverlapping groups yield grouped selection, while overlapping groups can encode hierarchical selection.The L1/L∞ combinations are described as computationally convenient for these structured-selection problems.
- Simulations showed CAP could reduce model error relative to LASSO in small-n-large-p settings, including noisy groupings with estimated group counts between 50% and 150% of the truth.The conclusion concerns grouped-selection experiments with data-determined groups.
- iCAP used degrees of freedom parsimoniously, and CAP estimates were more interpretable because they respected supplied group or hierarchical structure.The paper also reports improved prediction with similar or smaller group counts in additional examples.
- The framework assumes grouping or hierarchical information is available, while completely data-driven structure estimation is left for future research.The table summary also reports hierarchical models with reduced error and sparser models, with small BLASSO-related discrepancies.
APPENDIX A: PROOFS
The appendix proves convexity of the CAP penalty by verifying positive homogeneity and the triangle inequality. These properties establish convexity through the standard convex-combination argument.
- The proof reduces convexity of T to positive homogeneity and the triangle inequality.
- For every scalar α, group norms scale as N_k(αβ) = αN_k(β), yielding T(αβ) = |α|T(β).
- The triangle inequality gives T(β1 + β2) ≤ T(β1) + T(β2).
- Setting β1 = θβ3 and β2 = (1 − θ)β4 for θ ∈ [0,1] establishes convexity.
A.1. DF Estimates for iLASSO and iCAP.
The appendix derives degrees-of-freedom estimates for iLASSO and iCAP fits along the regularization path using local projection behavior and Stein’s lemma. For the L∞-penalized fit, df(λ) equals E[|Uλ|] + 1.
- The analysis studies iLASSO and iCAP fits along the regularization path, leveraging duality with the LASSO problem.
- Away from finitely many hyperplane-defined breakpoints, the active sets and related path regions are locally invariant.
- Locally, the fitted values behave as projection onto a fixed subspace, making the fit uniformly Lipschitz and allowing its divergence to be calculated.
- For the L∞-penalized fit, the degrees of freedom are df(λ) = E[|Uλ|] + 1.
- The nonoverlapping-group proof follows the same steps, using convexity and continuity of the CAP objective plus local invariance between breakpoints.
APPENDIX B: PSEUDO-CODE FOR THE ICAP ALGORITHM
The iCAP algorithm traces the regularization path by updating active groups and advancing coefficients until the next breakpoint. Breakpoints occur when group conditions or residual-related conditions change, with the smallest positive step determining the next update.
- iCAP initializes at the largest group score with zero coefficients, then iterates until the regularization parameter reaches zero.The initial parameter is λt = maxk ∥ck(0)∥, with β̂(λt) = 0.
- At each iteration, groups attaining the current threshold are active; inactive groups receive no coefficient update.Active groups update along αk · Sλ,k, with αk chosen to satisfy the algorithm’s condition.
- The algorithm computes candidate positive step sizes for active-group entry, active-group changes, and residual-related events.These candidates include equality of group scores and residual conditions for groups inside or outside the active set.
- The smallest breakpoint step, including the remaining λ, advances the coefficient path and sets the next regularization value.An empty candidate set contributes +∞, while the update uses δ = min{δA,δI,δR,δU,δS,λt}.