Abstract
We consider the empirical risk minimization problem for linear supervised learning, with regularization by structured sparsity-inducing norms. These are defined as sums of Euclidean norms on certain subsets of variables, extending the usual $\ell_1$-norm and the group $\ell_1$-norm by allowing the subsets to overlap. This leads to a specific set of allowed nonzero patterns for the solutions of such problems. We first explore the relationship between the groups defining the norm and the resulting nonzero patterns, providing both forward and backward algorithms to go back and forth from groups to patterns. This allows the design of norms adapted to specific prior knowledge expressed in terms of nonzero patterns. We also present an efficient active set algorithm, and analyze the consistency of variable selection for least-squares linear regression in low and high-dimensional settings.
Introduction
In modern high-dimensional data analysis, the number of features ($p$) often significantly exceeds the number of observations ($n$). While standard techniques like the Lasso ($\ell_1$-regularization) address this by inducing sparsity, they are typically "structure-blind," treating every variable as independent. In many real-world applications—such as fMRI neuroimaging, genomics, or sensor networks—variables possess inherent relationships, such as spatial contiguity or hierarchical dependencies. This paper introduces a framework for linear supervised learning that uses overlapping groups of variables to enforce specific, structured sparsity patterns, allowing researchers to encode complex prior knowledge directly into the regularization process.
Methods: Structured Sparsity-Inducing Norms
The core of the proposed approach is the use of Structured Sparsity-Inducing Norms. Unlike the standard Group Lasso, which operates on disjoint sets, this framework generalizes to overlapping groups.
The norm $\Omega(w)$ is defined as the sum of the $\ell_2$-norms of subsets (groups) of variables. Because these groups can overlap, a single variable can be penalized multiple times as part of different groups. The authors establish a formal link between a set of "groups" and the resulting "nonzero patterns" (the sets of variables the model is allowed to select):
- Backward Procedure: Given a desired set of patterns (e.g., rectangular blocks of pixels), this algorithm reverse-engineers the minimal set of groups required.
- Forward Procedure: This determines which patterns a given set of groups will induce.
To handle the computational complexity of solving these problems for large $p$, the authors developed an Active Set Algorithm. This solver starts with an empty set of variables and incrementally adds only those that violate optimality conditions, significantly outperforming generic Second-Order Cone Programming (SOCP) solvers.
Key Insights: The Hull Property and Weighting
A critical discovery in this work is the "Hull" Property. When groups overlap, the norm does not merely select variables; it selects the "G-adapted hull" of the variables. For instance, if groups are defined as half-planes on a 2D grid, the model naturally selects the convex hull of the relevant features.
Furthermore, the authors emphasize that weighting matters. They introduce a "W3" weighting scheme to account for variables appearing in multiple groups, ensuring that the penalty is balanced across the feature space. They also demonstrate that for a set of patterns to be representable by these norms, the set must be closed under intersection, providing a clear mathematical boundary for the types of prior knowledge that can be encoded.
Results and Performance
The framework was evaluated using synthetic datasets mimicking 1D sequences and 2D grids. The "Structured Lasso" (Slasso) significantly outperformed standard Lasso when the underlying signal was structured, particularly as the "hull" of the true variables became more densely populated.
Computationally, the active set algorithm showed a dramatic improvement. In empirical tests, while a standard SOCP solver's complexity scaled at roughly $O(p^{2.13})$, the active set algorithm scaled at approximately $O(p^{0.45})$. Finally, the authors proved that the model consistently recovers the correct hull of relevant variables in both low and high-dimensional settings.
Conclusion and Future Work
This work provides a systematic way to bridge the gap between prior structural knowledge and sparse regularization. While the current framework requires the structure to be known beforehand, future research may explore methods to learn these structures from data. Additionally, investigating non-convex formulations or combining this approach with stability selection could further enhance the reliability and aggressiveness of variable selection in complex domains like bioinformatics and neuroimaging.
Summary updated