Structured Variable Selection with Sparsity-Inducing Norms

Rodolphe Jenatton; Jean-Yves Audibert; Francis Bach

Source-linked AI summary

Structured Variable Selection with Sparsity-Inducing Norms

Rodolphe Jenatton, Jean-Yves Audibert, Francis Bach

arXiv:0904.3523v3Apr 22, 2009stat.ML

TL;DR

The paper asks how linear supervised learning can use prior knowledge about structured nonzero-variable patterns rather than treating variables independently. It analyzes overlapping-group sparsity norms, designs groups from desired patterns, and develops optimization and selection guarantees. The resulting method supports structured patterns, with experiments showing better prediction when the prior matches the generating pattern, while relying on a restricted norm formulation and active-set behavior with specific scope boundaries.

Problem
Ordinary ℓ1 regularization disregards relationships among variables, motivating sparsity penalties that encode more sophisticated prior knowledge about expected nonzero patterns.
Method
The paper studies sums of weighted Euclidean norms over possibly overlapping groups, characterizes their induced patterns, reverse-engineers minimal groups for target patterns, and provides an active set algorithm.
Results
The framework yields allowed patterns equal to their group-defined hull, and experiments show structured methods outperform Lasso when the generating-pattern prior is relevant.
Takeaways & Limitations
Structured norms can incorporate prior knowledge into linear variable selection, with prediction benefits depending on the relevance of that prior information.
Takeaways & Limitations
The studied formulation uses diagonal group weights and leaves non-diagonal positive-definite group weighting for future work.

Abstract

from arXiv · show

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.

1. Introduction

The paper develops structured sparsity norms to encode prior knowledge about nonzero-variable patterns that ordinary ℓ1 regularization disregards. It characterizes the patterns induced by overlapping groups and provides procedures for designing norms adapted to target patterns.

Motivation: Ordinary ℓ1 regularization treats variables independently, disregarding spatial, hierarchical, and problem-specific relationships that may aid interpretability or prediction.The paper motivates structured penalties with examples from neuroimaging, face recognition, computer vision, and bioinformatics.
Motivation: Structured sparsity-inducing norms are motivated by applications whose discriminative variables form localized, convex, contiguous, or bounding-box-like patterns.These patterns arise in brain imaging, occluded-face recognition, object detection, and genomic profiles.
Prior knowledge: Unlike ℓ1 and partition-based group norms, overlapping groups can encode richer prior knowledge about the allowed nonzero patterns.Earlier hierarchical methods considered overlapping nested groups in trees and directed acyclic graphs, whereas this paper studies all possible group sets.
Contributions: The paper provides forward and reverse procedures between groups and patterns, including a unique minimal group set for a prescribed family of nonzero patterns.This supports automatic construction of sparsity-inducing norms adapted to target structures.
Contributions: For each group set, the paper characterizes allowed patterns through a hull and shows that valid nonzero patterns are exactly those equal to their hull.On a two-dimensional grid, the hull can be an axis-aligned bounding box or the regular convex hull.

2. Regularized Risk Minimization

The framework regularizes convex empirical risk minimization with sums of weighted Euclidean norms over possibly overlapping variable groups. It contains standard penalties as special cases while inducing structured group-level sparsity.

Risk minimization: The model predicts Y from X ∈ R^p using n observed input-response pairs and a convex, continuously differentiable loss.Examples include square loss for least-squares regression and logistic loss for binary classification.
Structured norms: The regularizer sums weighted ℓ2-norms over a spanning collection of variable subsets, which may overlap rather than form a partition.A variable can belong to multiple groups and receive different weights in those groups.
Special cases: The framework includes the ℓ2-norm, Lasso, Elastic Net, group-Lasso, and hierarchical norms as special cases determined by the chosen groups.Singleton groups yield the Lasso, partitions yield group-Lasso, and tree or DAG embeddings yield hierarchical norms.
Regularized objective: The paper’s objective combines empirical loss with a regularization parameter µ and uses non-squared ℓ2-norm combinations to induce sparsity and specific coefficient patterns.The authors position the general formulation as extending standard penalties toward richer prior knowledge.

3. Groups and Sparsity Patterns

The structured norm determines a restricted family of stable sparsity patterns through unions of overlapping groups, while its hull characterizes the nearest allowed pattern. The paper provides algorithms to characterize, reverse-engineer, and efficiently compute these patterns, with consistency and uniqueness results under stated conditions.

Stable Patterns Generated by G: The norm induces group sparsity, with zero patterns formed by unions of selected groups and nonzero patterns obtained by complementing those unions.The ℓ2 penalty encourages entire grouped subvectors to vanish, while within-group ℓ2 norms do not promote individual sparsity.
Stable Patterns Generated by G: The paper also gives uniqueness conditions: an invertible Gram matrix or inclusion of the full variable set as a group ensures a unique solution.The Gram-matrix condition requires p ≤ n, whereas suitable group connectivity can ensure uniqueness in high-dimensional settings.
Stable Patterns Generated by G: Under the paper’s regularity assumptions, sparse solutions almost surely have zero patterns in the union-closure Z of the groups.If the Gram matrix is invertible, the solution is unique and its zero pattern belongs to Z almost surely.
General Properties of G, Z and P: The allowed pattern family is intersection-closed for nonzero patterns and union-closed for zero patterns, constraining which prior structures can be encoded.Reverse-engineering a target family therefore requires intersection closure or produces its intersection-closure instead.
From Patterns to Groups: A unique minimal group set can be obtained by pruning groups that are unions of other groups, reducing representation size and computational complexity.The backward pruning algorithm has complexity O(p|Z|^2) and can reduce exponentially many candidate groups to polynomially many.
General Properties of G, Z and P: The G-adapted hull is the smallest allowed nonzero pattern containing a given variable set, becoming an axis-aligned bounding box or regular convex hull in grid constructions.Equality with the input set holds exactly when that set is already an allowed pattern.

4. Optimization and Active Set Algorithm

The paper develops an active set algorithm that solves structured sparsity problems on progressively larger variable sets and checks global optimality through duality. It reduces computational cost when the final active set is small, while retaining exact or certified solutions under stated conditions.

Computational motivation: Generic SOCP solving has complexity O(p^3.5 + |G|^3.5) for one regularization value, making it unsuitable when variables or groups are numerous.The active set method targets this computational bottleneck.
Active set strategy: The active set algorithm solves reduced problems over increasingly larger sets and checks global optimality using duality-based conditions.Variables outside the current active set are constrained to zero, and optimality is monitored through the duality gap.
Complexity: For rectangular groups, total complexity is O(s max{p^1.75, s^3.5}), and simulations find the active set strategy useful when s is much smaller than p.The strategy is not advantageous when s ≈ p or when p is very small; a first-order solver gives O(sp^1.5).
Scope: The paper extends the active set approach to general overlapping groups while deferring specialized SOCP solver design to future work.The presented algorithm relies on a black-box SOCP solver, including first-order and SOCP implementations.
Optimality conditions: The reduced primal and dual problems satisfy strong duality, enabling optimality certification for candidate active sets.The full-problem gap is evaluated after padding the reduced solution with zeros.
Optimality conditions: Computing the exact dual norm is as hard as the original problem, so the algorithm uses upper and lower bounds on the dual norm to control the gap.The reduced problem's gap can vanish up to solver precision, while the full problem requires additional certification.
Algorithm behavior: The heuristic may skip the exact optimal active set, but a slightly larger active set still yields the correct nonzero pattern when sufficient condition (S0) holds.The algorithm retains an upper bound on the duality gap and converges to an optimal solution or reaches all p variables.

5. Pattern Consistency

The paper derives conditions under which the structured estimator consistently recovers the hull of the true nonzero pattern, including low- and high-dimensional settings. These conditions extend Lasso and group-Lasso consistency while controlling the structured pattern family.

The analysis targets consistent recovery of the generating pattern’s hull, because other patterns occur with probability zero under the framework.
Low-dimensional analysis: The low-dimensional result gives necessary and sufficient conditions for consistent hull estimation under fixed design and Gaussian-noise assumptions.
The guarantees are scope-limited to square loss with fixed design, and stronger position assumptions may improve scaling in problem-dependent ways.
The consistency conditions naturally extend the corresponding results for the Lasso and group Lasso.
High-dimensional analysis: The high-dimensional result assumes the consistency condition and bounds the probability of incorrect hull selection using group-, signal-, and hull-related constants.
In the Lasso case, the constants yield the usual scaling n ≈ log p and µ ≈ σ(log p/n)^1/2, while the structured framework additionally controls allowed nonzero patterns.

6. Experiments

Experiments evaluate structured sparsity on sequence and grid problems, showing that overlap-aware weighting and ISlasso are important for recovering useful patterns. When the structural prior is relevant, the structured methods can outperform Lasso and substantially reduce computation.

Experimental setup: Experiments evaluate Slasso and ISlasso on noisy linear models with contiguous sequence patterns and convex grid patterns.
Weighting: Overlap-aware weights are important: uniform and size-dependent weights perform poorly, often failing to recover the correct nonzero patterns and sometimes selecting every variable.
Weighting: ISlasso reduces problems caused by many overlapping groups while retaining desirable effects of overlap.
Prediction error and prior relevance: Adding ±π/4-groups to rectangular groups produces patterns closer to the generating pattern on grid experiments.
Prediction error and prior relevance: When the structural prior is relevant and the hull contains few zero variables, Slasso and ISlasso outperform Lasso; their sample complexity depends on hull size rather than nonzero count.
Prediction error and prior relevance: The structured approach is not always dramatically better in prediction, but it offers greater interpretability.
Computational cost: The active set algorithm has empirical complexity ≈O(p^0.45), compared with ≈O(p^2.13) for the SOCP solver, at the same performance level.

7. Conclusion

The paper presents a framework for encoding structured nonzero patterns through overlapping-group norms, together with algorithms and consistency guarantees. It identifies intersection-closed pattern families and outlines extensions to broader structures and learning tasks.

The method incorporates prior knowledge about sparse-pattern form through a regularizer combining Euclidean norms of possibly overlapping variable groups.
The framework yields intersection-closed families of nonzero patterns, including all rectangles on a two-dimensional grid.
The paper studies group design, efficient algorithms, and theoretical guarantees for structured sparsity-inducing methods.
Future work includes bootstrapping, broader pattern families, and applications to multiple kernel learning, multitask learning, and sparse matrix factorization.

Appendix A. Proof of Proposition 1

The appendix proves uniqueness of the optimization solution under positive-definite design or suitable group-connectivity assumptions. The proof uses convexity and strict convexity of the loss along relevant segments.

With invertible Q, the loss is strictly convex, so adding the convex structured penalty yields a unique minimizer.
When the full variable group belongs to G, uniqueness follows by contradiction from the penalty’s linearity properties and strict convexity of the loss.
The argument extends to the weaker condition that every pair of variables occurs together in some group.

Appendix B. Proof of Theorem 2

The proof shows that datasets producing solutions with a prohibited zero pattern have probability zero. It uses strict convexity, the implicit function theorem, and a measure-zero argument.

Proof setup: The contradiction assumes a pattern I with |I| ≤ k − 1 occurs with positive probability despite Ic not belonging to Z.An index α in Hull(I) \ I is added to form J, while the active groups determine the restricted problem.
Restricted optimization: Full-rank XJ makes the restricted loss strictly convex, yielding a unique stationary minimizer for each relevant response vector.The restricted objective is continuously differentiable near the solution, and its Hessian is positive definite.
Implicit-function argument: The implicit function theorem represents the stationary solutions locally as a differentiable graph, with one response coordinate determined by the others.A nonzero derivative of ψα with respect to y1 permits the representation y1 = ϕ(y2, . . . , yn).
Measure-zero argument: Each local solution set has zero Lebesgue measure because it is contained in a graph, and Fubini’s theorem handles the resulting sections.The argument uses that singletons in Rn have zero Lebesgue measure.
Conclusion: Compact covering and regularity extend the local zero-measure result to EI, contradicting the assumption that P(EI) > 0.A finite collection of local balls covers every compact subset, after which Lebesgue-measure regularity yields P(EI) = 0.

Appendix C. Proof of the minimality of the Backward procedure (see Algorithm 1)

The minimality proof establishes that the backward procedure returns a base that spans the desired zero-pattern family and cannot be reduced while preserving that property.

Proof goals: The proof separates the claim into showing that G spans Z and that G is minimal.These are the two defining properties established for the output of the backward procedure.
Spanning: A recurrence on DAG depth shows that the generated groups represent every pattern in Z up to the current depth.Each pattern is either itself a group or a union of strictly smaller patterns, with initialization at the smallest pattern size.
Minimality: Minimality follows by contradiction: removing any group would require another base group to span Z while being strictly contained in G.The proof then selects an element e excluded from the smaller base and derives a forbidden decomposition.
Minimality: The proposed reduction is impossible because members of G are constructed not to be unions of other elements of Z.Thus no strictly smaller spanning base exists.

Appendix D. Proof of Proposition 3

The proposition derives primal-dual optimality conditions for the restricted structured-sparsity problem using Fenchel duality and the dual norm.

Dual formulation: Fenchel duality supplies the primal-dual formulation and establishes existence under a nonempty continuity domain.The relevant domain intersects the effective domains of the conjugate regularizer and the loss.
Optimality conditions: When the loss is differentiable, optimality is characterized by the gradient of the restricted loss and the subdifferential of the restricted norm.The condition uses ∂ΩJ(wJ) together with ∇LJ(wJ).
Equivalence: Fenchel-Young equality and the dual-norm definition convert the optimality relation into the proposition’s equivalent primal-dual equations.The derivation connects the regularizer value with the squared dual norm term.

Appendix E. Proofs of Propositions 4 and 5

The proofs establish full-problem optimality conditions by completing restricted solutions with zeros and bound the resulting duality gap using the group structure.

Restricted-to-full optimality: Completing the restricted solution with zeros and setting κ = −∇L(w) connects restricted optimality to a duality gap for the full problem.The restricted and full gradients agree on J, allowing the gap to be evaluated from the completed vector.
Optimality characterization: Full optimality is equivalent to a condition over all perturbations, which can be projected onto variables that may enter the active set.The projection is organized by admissible patterns K in ΠP(J).
Dual-norm bound: The group structure reduces the projected dual-norm calculation to groups outside the currently active groups, though the relevant norm lacks a closed form.The proof therefore replaces it with an upper bound based on the group decomposition.
Accuracy guarantee: A sufficient condition for ε-accuracy follows by bounding the full duality gap through restricted and complementary dual norms.The complementary term is controlled using the auxiliary lemma and the resulting inequality.
Final bound: The largest groups in the inactive fringe determine the maximum values used in the final dual-norm bound.The fringe consists of inactive groups not contained in any larger inactive group.

Appendix F. Proof of Theorem 6

The proof establishes necessary and sufficient conditions for consistent selection by analyzing the reduced problem on the true hull and verifying optimality for the full problem.

Necessary condition: The rescaled estimation error ˆ∆ converges in probability to the unique minimizer ∆∗ of a strictly convex limiting objective.Strict convexity follows from Q ≻ 0.
Sufficient condition: The sufficient condition proves that the padded reduced solution satisfies the full optimality condition and is therefore optimal for the full problem.The conclusion uses the inactive-variable inequality together with the reduced problem analysis.
Necessary condition: The reduced estimator ˆwJ consistently estimates the true vector wJ, and padding it with zeros consistently estimates the hull of w.The active variables are identified through the hull of the nonzero coordinates.
Necessary condition: Optimality on the active variables is verified through the condition ∇L(ˆw)J + µ ˆrJ = 0.This establishes the required condition relative to J before inactive-variable inequalities are checked.
Sufficient condition: The remaining inactive-variable conditions are controlled using the gradient expression, convergence of Q and ˆrJ, and vanishing noise terms q = op(1).These controls complete the argument that the padded estimator is optimal for the full problem.

Appendix G. Proof of Theorem 7

The proof derives high-probability conditions for exact hull selection by analyzing the reduced problem, controlling Gaussian fluctuations, and verifying full optimality conditions.

High-probability control: The structured norm’s dual complexity is controlled through expected dual norms; for the Lasso, this quantity is of order (log p)1/2.The proof also introduces operator norms and Gaussian comparison tools to obtain the theorem’s bound.
Reduced problem and hull selection: The reduced problem on the hull J is used to show that every relevant active group is selected, so the estimator’s active-set hull equals J.The argument relies on the smallest nonzero coefficient ν and establishes that no active group is missing.
Full-problem optimality: The estimator padded with zeros on Jc is optimal for the full problem once the active and inactive optimality conditions are satisfied.The proof reduces the remaining task to verifying inequalities for inactive variables.
Full-problem optimality: Positive definiteness of Q makes the relevant Schur-complement diagonal terms less than one, enabling control of inactive-variable contributions.This matrix property is used in the inactive-gradient analysis.
High-probability control: Gaussian concentration inequalities bound the tail probabilities of the noise-dependent quantities needed for the selection conditions.The proof treats qJc|J as a centered Gaussian vector and applies concentration for Lipschitz functions and standard Gaussian variables.
First-order optimization: Variational reformulations yield an alternating first-order optimization scheme between w and the group variables, with closed-form updates in the square-loss case.The scheme supports warm restarts and can substantially accelerate computation along regularization paths.
Dual characterization: The dual norm is derived through conic duality as an SOCP satisfying Slater’s conditions and strong duality, but its preceding optimization problem lacks a closed-form solution.The proof therefore studies a different but closely related problem.