Multi-Layer Feature Reduction for Tree Structured Group Lasso via Hierarchical Projection
Tree structured group Lasso (TGL) is a powerful technique in uncovering the tree structured sparsity over the features, where each node encodes a group of features. It has been applied successfully in many real-world applications. However, with extremely large feature dimensions, solving TGL remains a significant challenge due to its highly complicated regularizer. In this paper, we propose a novel MultiLayer Feature reduction method (MLFre) to quickly identify the inactive nodes (the groups of features with zero coefficients in the solution) hierarchically in a top-down fashion, which are guaranteed to be irrelevant to the response. Thus, we can remove the detected nodes from the optimization without sacrificing accuracy. The major challenge in developing such testing rules is due to the overlaps between the parents and their children nodes. By a novel hierarchical projection algorithm, MLFre is able to test the nodes independently from any of their ancestor nodes. Moreover, we can integrate MLFre-that has a low computational cost-with any existing solvers. Experiments on both synthetic and real data sets demonstrate that the speedup gained by MLFre can be orders of magnitude.
The authors present a node screening method for tree-based regularization which identifies inactive nodes (i.e. nodes the features of which have all zero coefficients) in a top down manner given the tree that defines the groups of variables. As usual the idea is to work with the sub-gradient of the regularizer, if the subgradient with respect to a node is in the strict set of subgradient at 0, then this node is set to zero. The problem in tree based group lasso is that it is hard to access the subgradient of each node, since we only have access at the mixture of the subgradients with respect to all nodes. The authors provide a method to project the mixture of subgradients at each node and examine if the subgradient falls in the region which give us sparsity, if yes then by eliminating that corresponding node we remove those inactive features.The proposed method makes the use of tree structured lasso on datasets with tens of thousands, or even hunderds of thousands of attributes.  The authors start by deriving the dual of the tree group lasso (which is equivalent to a projection problem on the feasible set), with dual variable $\vect \theta$ and feasible set F={$X^T \theta$ in the subdifferential at zero of the tree norm}. They start with the observation that some $\theta$ will be a part of the feasible set if $X^T\theta$ is on the feasible set and thus its projection on the feasible set is $X^\theta$ and they provide an hierarchical algorithm that given a vector $z$ projects it on the feasible set. The algorithm works by hierarchically decomposing the projection on the subdifferential at zero to a projection on the sum of two sets: the bounded norm ball set B and the sum of the sets of the bounded norm balls of all of each children nodes. The sizes of the norm balls are given by the importance, w^i_j, of the respective nodes, G^i_j. Using the hierarchical projection algorithm they can decompose $X^T\theta^*$ at the optimal solution as a sum of vectors $\ksi_j^i$ where each $\ksi_j^i$ is in the sudifferential set of tree norm with respect to the G^i_j node of the tree at the optimal solution of the primal $\beta^*$. Thus if one knows $X^T\theta^*$ then one can compute the inactive nodes, G_j^i, by looking at the $\ksi^i_j$ that are within the respective bounded radius ball. However since $\theta^*$ is not known the authors define a set that contains the optimal solution and solve for an upper bounding problem, providing along the way a close-form solution for the non-convex supremum problem.The screening rule takes as input a sequence of hyperparameters $\lambda$ and for each sub-sequent pair outputs the corresponding inactive nodes of the tree, i.e. thoese the supremum problem of which is smaller than the radius of the ball of the respective node.  The authors provide a small set of experiments on one artificial and one real-world dataset in which the method consistently offers a speedup of around 40 times. The paper is well written but not easy to follow, especially for someone who is not well-versed into optimization namely because it is quite technical consisting of a series of lemmas and theorems (just the appendix with the respective proofs is more than 20 pages).Given the amount of the material and the NIPS space limitations I am not sure it would have been possible, even though desirable, to give a more high level picture/intuitive picture of the basic components of the algorithm before going into the technical details. There seems to be a problem in the proof of Theorem 7. The definition of lambda max is in contradiction to ii) in that theorem, i.e. \lambda_max is the largest value that keeps y/\lambda in the feasible set, however in ii) we have y/\lambda \in F is equivalent to \lambda \geq \lamnbda_max. Page 5 column 218 what is the \Ksi^i_j set?On R1,2^* since these are supremums how often do we expect to see sup'>'w_j^i while the node is in fact inactive? any insights from the theory or experimental results?