Lasso Screening Rules via Dual Polytope Projection
Lasso is a widely used regression technique to find sparse representations. When the dimension of the feature space and the number of samples are extremely large, solving the Lasso problem remains challenging. To improve the efficiency of solving large-scale Lasso problems, El Ghaoui and his colleagues have proposed the SAFE rules which are able to quickly identify the inactive predictors, i.e., predictors that have 0 components in the solution vector. Then, the inactive predictors or features can be removed from the optimization problem to reduce its scale. By transforming the standard Lasso to its dual form, it can be shown that the inactive predictors include the set of inactive constraints on the optimal dual solution. In this paper, we propose an efficient and effective screening rule via Dual Polytope Projections (DPP), which is mainly based on the uniqueness and nonexpansiveness of the optimal dual solution due to the fact that the feasible set in the dual space is a convex and closed polytope. Moreover, we show that our screening rule can be extended to identify inactive groups in group Lasso. To the best of our knowledge, there is currently no "exact" screening rule for group Lasso. We have evaluated our screening rule using many real data sets. Results show that our rule is more effective in identifying inactive predictors than existing state-of-the-art screening rules for Lasso.
The authors develop exact screening rules for the 
      Lasso and Group Lasso problems (with quadratic loss). These rules are 
      based on the observation that the dual of these problems is simply the 
      projection of a vector onto a convex polytope. They can be applied in a 
      sequential fashion along a grid of tuning parameter values. 
      Quality: This is an excellent paper. The idea is elegant 
      and explained well, and the resulting method appears to be highly 
      effective. Clarity: Very good. Originality: 
      While the main idea is not greatly different from the SAFE rules, 
      the authors have simplified the idea and made it work better. 
      Significance: This seems like work that could be easily 
      built on. While the "exact" aspect of DPP is nice, the strong rules paper 
      makes the point that their rule often just works (even though it requires 
      checking the KKT conditions). It would be helpful to see the strong rule 
      compared in the empirical studies. Of course for the strong rules you'd 
      need to report whether it threw out any variables it should not have (and 
      if so, perhaps show how many false rejections there were). Regardless of 
      the results, DPP is still significant for being the best Comments: 
      It is easy to prove that the DPP rule (at lambda_max) is strictly 
      better than the SAFE rule, though I don't think you come out and say this. 
      To compare the two, notice that DPP can be written as |x_i^T y | 
      < lambda_max - ||x_i|| ||y|| (lamda_max - lambda) / lambda 
      Comparing the RHS of DPP and SAFE are identical except for two 
      differences. Both of these differences make RHS's DPP larger than SAFE and 
      therefore it can screen strictly more features than SAFE. Minor 
      comments: - Equation 8: Fix RHS. - Equations 21,22: Fix LHS 
      (should be L2 norms) - Line 346: "projection ratio" should be 
      "rejection ratio" ? - Line 376: "verfying" typo - Lines 406-7: 
      highly correlated with the response, you mean?