Two-Layer Feature Reduction for Sparse-Group Lasso via Decomposition of Convex Sets
Sparse-Group Lasso (SGL) has been shown to be a powerful regression technique for simultaneously discovering group and within-group sparse patterns by using a combination of the 1 and 2 norms. However, in large-scale applications, the complexity of the regularizers entails great computational challenges. In this paper, we propose a novel two-layer feature reduction method (TLFre) for SGL via a decomposition of its dual feasible set. The two-layer reduction is able to quickly identify the inactive groups and the inactive features, respectively, which are guaranteed to be absent from the sparse representation and can be removed from the optimization. Existing feature reduction methods are only applicable for sparse models with one sparsity-inducing regularizer. To our best knowledge, TLFre is the first one that is capable of dealing with multiple sparsity-inducing regularizers. Moreover, TLFre has a very low computational cost and can be integrated with any existing solvers. Experiments on both synthetic and real data sets show that TLFre improves the efficiency of SGL by orders of magnitude.
--- Summary ---This paper generalizes the screening procedure  to  the sparse group lasso problem where it is able to identify  inactive groups and inactive features (i.e., features with zero weight in the optimal solution) simultaneously before optimization and consequently to accomplish dimensionality reduction. Therefore, when used as a per-processing step in sparse group lasso problem to reduce its scale,  the computational complexity of the optimization problem can be reduced significantly without sacrificing the accuracy of the model. --- Contributions and overall evaluation ---To apply the typical screening methods, one needs to  estimate the optimal dual solution  of the original optimization problem. For sparse group lasso, the feasible set is an intersection of ellipsoids and it turns out that the dual estimation is a difficult task.  The basic idea  to remedy this difficulty is to utilize Fenchel's duality to derive an elegant decomposition of the dual feasible set (i.e., sum of simple convex sets due to the pretense of multiple sparsity inducing regularizes) to be able to estimate the dual objective. The paper does survey related work appropriately and is clearly written.  The paper technically sound and the proofs seem to be correct.  It is clear, of high quality, novel, definitely of significance.  However, more effort can be put into making the proofs more understandable (though many of the explanations are very good) and extending the experiments. -- Minor comments --- - Line 181, Page 4, by --> By- Line 527, Page 10, |\beta|_1 --> |\beta_g|_1