关键词: Lasso算法, Screening加速技巧, 稀疏特征选择, 高维数据

Abstract: Recently, Lasso is one of the most popular algorithms for sparse feature selection in the application. Traditional Lasso algorithm reduces the computational overhead to a certain extent through feature selection. However, sometimes it may become impossible to load the data matrix into the main memory of the computer when the feature dimension or the number of samples is extremely large. Thus it can be seen that there are still many difficulties and challenges in solving Lasso algorithm. To address these challenges, the Screening accelerating technique has been proposed and becomes the research focus in recent years. The Screening technique is able to quickly identify and remove the invalid features before the optimization process. Then it only needs to deal with the reduced data, which can greatly accelerate the solving efficiency. The most important is that the Screening technique can guarantee that the discarded features have zero coefficients in the solution vector so as to reduce the data dimension as well as maintain the solution accuracy. This paper firstly derives the dual problem of Lasso, then introduces the Screening accelerated technique according to the properties of the dual problem. Besides, it evaluates the performance of the algorithms under several high dimensional datasets using three metrics, speedup ratio, detection rate and running time. Results show that the Screening accelerated technique is effective in solving efficiency of Lasso.

Key words: Least absolute shrinkage and selection operator（Lasso）, Screening accelerating technique, sparse feature selection, high-dimensional data