Simultaneous Safe Screening of Features and Samples in Doubly Sparse Modeling
This work addresses efficiency in sparse modeling for machine learning practitioners, but it is incremental as it builds on existing safe screening techniques.
The paper tackles the problem of learning sparse models by introducing a method for simultaneously screening features and samples, which improves efficiency by exploiting synergy between the two processes. The result is demonstrated through numerical experiments on large-scale problems, showing practical advantages.
The problem of learning a sparse model is conceptually interpreted as the process of identifying active features/samples and then optimizing the model over them. Recently introduced safe screening allows us to identify a part of non-active features/samples. So far, safe screening has been individually studied either for feature screening or for sample screening. In this paper, we introduce a new approach for safely screening features and samples simultaneously by alternatively iterating feature and sample screening steps. A significant advantage of considering them simultaneously rather than individually is that they have a synergy effect in the sense that the results of the previous safe feature screening can be exploited for improving the next safe sample screening performances, and vice-versa. We first theoretically investigate the synergy effect, and then illustrate the practical advantage through intensive numerical experiments for problems with large numbers of features and samples.