GAP Safe screening rules for sparse multi-task and multi-class models
High dimensional regression benefits from sparsity promoting regularizations. Screening rules leverage the known sparsity of the solution by ignoring some variables in the optimization, hence speeding up solvers. When the procedure is proven not to discard features wrongly the rules are said to be safe. In this paper we derive new safe rules for generalized linear models regularized with 1 and 1 { 2 norms. The rules are based on duality gap computations and spherical safe regions whose diameters converge to zero. This allows to discard safely more variables, in particular for low regularization parameters. The GAP Safe rule can cope with any iterative solver and we illustrate its performance on coordinate descent for multi-task Lasso, binary and multinomial logistic regression, demonstrating significant speed ups on all tested datasets with respect to previous safe rules.
Summary:This paper presents an unprecedentedly fast method for eliminating variables during iterations of multi-task group lasso that is provably safe, meaning that all variables that are eliminated would ultimately obtain zero weights when running vanilla group lasso.This method is iterative; as the primal solver converges, it eliminates an increasing number of variables.The authors compare their method to previous methods and demonstrate that all previous methods are either unsafe or are substantially slower for small duality gaps.The authors describe how their method should be applied to specific cases of group lasso, including l1 and l1/l2 regularized logistic regression, and present real applications where their method achieves a substantial speed-up over vanilla group lasso and an existing method for small duality gap thresholds.General suggestions: 1. The primary situation where this method obtains substantial speed improvements over alternatives is where the duality gap threshold is extremely small.To make the importance of the work more convincing, the authors need to demonstrate that this is a common situation or at least a situation that occurs in some important group lasso settings.If the duality gap must be small in one of the real examples the author use in Section 4, then stating this and providing a citation for it would be sufficient. 2. Some of the derivations skipped many steps.The paper would be much easier to follow if these derivations were fleshed out in more detail, either in the main text or in the Supplement.I have noted the places where this was the case in "Specific comments and suggestions." 3. There are many grammar and word choice errors, including in the statements of many of the propositions.To make the paper sufficiently clear for readers to grasp what the authors have accomplished, the authors need to fix these errors.I have pointed out the most problematic ones in "Specific comments and suggestions."Specific comments and suggestions, main text: 1. In the Introduction, the authors discuss the lasso problem.In Section 2, they discuss the group lasso problem.They should explicitly state that the lasso is a specific case of the group lasso and maybe re-word the introduction to discuss the group lasso problem. 2. There is a missing citation in Remark 1 in Section 2.1. 3. The authors should cite Fermat's condition at the beginning of Section 2.2. 4. The authors should either derive the dual formulation of the group lasso that they present in Section 2.2 in the Supplement or cite the paper in which it was derived. 5. In the first "if and only if" statement in Section 2.3, I am convinced that 0 being a primal solution implies the next statement, but it is not obvious why the converse is true.The authors should justify the converse in more detail. 6. The authors should add a conclusion sentence to section 2.3 that summarizes what they have shown. 7. In the beginnings of the subsections of Section 2.6, the word "Remind" should be replaced with "Remember." 8. It is not obvious why the sentence "Since theta^(gamma) maximizes D_gamma..." near the beginning of Section 2.6 is true, so the authors should justify this in greater detail. 9. Remark 4, which refers to equation (15), should be moved after equation (15).It is also not obvious why the first sentence is true, so the authors should justify it in greater detail. 10. When summarizing the Dynamic GAP Safe rule in Section 2.6, the authors state that dynamic safe screening rules are "the most efficient."They either need to rigorously prove that making more efficient rules would be impossible or replace the phrase "the most efficient" with something like "more efficient than existing methods in practice." 11. The way that Proposition 1 in Section 2.6 is worded is very confusing, so the authors should re-word it. 12. In Remark 7, the authors say that the active set obtained by GAP safe rules allow the solver to "identify relevant features earlier."They should say what method they are comparing to.Do they mean "earlier than previous methods would?" 13. In Section 3, the authors frequently use a variable z.They should define z at the beginning of the section. 14. The authors should add conclusion sentences to Sections 3.1 and 3.2 that summarize what they have shown. 15. I am not sure if the formulation of the logistic regression in (12) in Section 3.3 is correct.I think that the y_i should be in front of the parentheses and that there should be a term for the other class. 16. I am not sure if the formulation of the multinomial logistic regression in (14) is correct.I think that the Y_i should be in front of the second summation. 17. It is not obvious why the final sentence of Section 3.3 is true, so the authors should justify it in greater detail. 18. It is not obvious why the final sentence of Section 3.4 before Remark 9 is true, so the authors should justify it in greater detail. 19. Table 1 in Section 3 should be referred to somewhere in the main text. 20. In Section 4, the authors describe how they implemented the GAP Safe rule.They should make the code publicly available so that others can easily use their algorithm when solving group lasso problems. 21. In each of the applications the authors describe in Section 4, the author should explain why the optimization problem they are using is the right way to solve the problems or cite papers that have these explanations. 22. The heatmaps in Figures 1-3 are confusing.They might be clearer if the axes went in the opposite directions.The authors should also explicitly label the color bars in the figures. 23. In Section 4 and elsewhere, the authors sometimes call their method "GAP SAFE (Sphere)" and sometimes call it "GAP Safe (dynamic)."The authors should either always use the same terminology or, if these methods are not the same, explicitly define them and state the difference. 24. In Section 4, the authors compare to different existing methods for different datasets.The authors should explain why they do not compare to every method for every dataset. 25. In Section 4.2, the authors should summarize the results presented in Figure 2 in the text. 26. In Section 4.2, the authors should describe the "safe rule close in spirit to the Slores itself" or refer to the description in the Supplement. 27. The sentence in Section 5 starting with "Extensions to other type" is confusing, so the authors should re-word it.Specific comments and suggestions, supplement: 1. The phrasing of Proposition 2 in Section A.1 is a little confusing, so the authors should re-word it. 2. In the second paragraph in Section B, the authors should replace "sure" with "safe." 3. It is not obvious why the last sentence of Section B is true, so the authors should explain it in greater detail. 4. The phrasing of Proposition 4 in Section C.1 is a little confusing, so the authors should re-word it. 5. In Section C.1, it is not obvious why the choice for alpha[theta] is optimal when r_gamma_t-1 = 0, so the authors should explain why this is true in more detail. 6. The phrasing of Proposition 5 in Section C.2 is a little confusing, so the authors should re-word it. 7. When deriving the bound on |alpha[theta']- alpha[theta]| in Section C.2, it is not obvious why the second and third inequality are true, so the authors should provide additional steps. 8. In section C.2, it was not obvious why the final inequality is true, so the authors should provide additional steps.