Safe Feature Screening for Generalized LASSO

Solving Generalized LASSO (GL) problems is challenging, particularly when analyzing many features with a complex interacting structure. Recent developments have found effective ways to identify inactive features so that they can be removed or aggregated to reduce the problem size before applying optimization solvers for learning. However, existing methods are mostly devoted to special cases of GL problems with special structures for feature interactions, such as chains or trees. Developing screening rules, particularly, safe screening rules to remove or aggregate features with general interaction structures, calls for a very different screening approach for GL problems. To tackle this challenge, we formulate the GL screening problem as a bound estimation problem in a large linear inequality system when solving them in the dual space. We propose a novel bound propagation algorithm for efficient safe screening for general GL problems, which can be further enhanced by developing novel transformation methods that can effectively decouple interactions among features. The proposed propagation and transformation methods are applicable with dynamic screening that can easily initiate the screening process while existing screening methods require the knowledge of the solution under a desirable regularization parameter. Experiments on both synthetic and real-world data demonstrate the effectiveness of the proposed screening method.