Difference-of-Convex Approximation Methods for the Affine Sparsity Constraints for Hierarchical Variable Selection

This paper studies a class of logical constraints that enforce pre-determined hierarchical relationships among the variables under a unified formulation. We consider the cases where subsets of variables form layers in a hierarchy, where an activation of a variable (with a nonzero value) is allowed only if its predecessors are active in the model. We exactly formulate the logical constraints as affine sparsity constraints (ASCs), then approximate the constraint set by employing sparsity-promoting functions as surrogates of the indicator function. We propose to extend the variants of difference-of-convex (DC) algorithms to solve the resulting DC programs with ASC approximations. The proposed methods are applied to existing statistical learning problems with logical conditions, including models with interaction effects and group-structured hierarchical selection. Our numerical results show that the ASC approximations can implement the required logical conditions in the model while achieving desirable prediction accuracy compared to existing methods.