Branchennorm

Branchennorm is a term used in machine learning and statistics to denote a structured sparsity-inducing norm defined for vectors whose components are organized in a branching, tree-like structure. It is designed to encourage sparsity that respects the hierarchy, yielding models where either an entire branch of features is selected or rejected, improving interpretability and reducing overfitting in hierarchical data.

A common formulation considers a rooted tree T with leaf indices L. Let x ∈ R^{|L|} be the vector of leaf coefficients, and for each node v define L(v) as the set of leaves in the subtree rooted at v. With positive weights α_v, the branchennorm is defined as BN(x) = ∑_{v ∈ V} α_v ||x_{L(v)}||_2. The collection {L(v)} forms a laminar (nested) family, which helps ensure convexity of BN. In practice, a two-level version is often used, combining a branch-level penalty with a secondary penalty on leaves (such as an l1 or l2 term) to control sparsity within surviving branches.

Properties and relationships: the branchennorm is a convex regularizer under a laminar group structure, and it is positively homogeneous and subadditive. It promotes hierarchical sparsity, tending to deactivate entire branches along with their descendants, which can lead to interpretable feature selections aligned with the tree structure. It is related to other tree-structured sparsity norms, such as tree-structured group lasso and hierarchical lasso, and it can be integrated into optimization via proximal gradient methods.

Applications: branchennorm has been used to regularize models with inherently hierarchical features, including decision-tree ensembles, parse-tree representations in natural language processing, gene expression data organized by pathways, and branched neural network architectures.

See also: group lasso, tree-structured sparsity, hierarchical lasso.