A greedy screening test strategy to accelerate solving LASSO problems with small regularization parameters
A greedy screening test strategy to accelerate solving LASSO problems with small regularization parameters
复制标题
DOI：
10.1007/s00500-019-04275-x
复制
发表时间：
2019-08
期刊：
影响因子：
4.1
通讯作者：
Hai-Wei Shen;Hua Chai;Liang-Yong Xia;Sheng-Bing Wu;Wei Qu;Yong Liang;Xiang-Tao Liu
中科院分区：
文献类型：
--
作者：
Hai-Wei Shen;Hua Chai;Liang-Yong Xia;Sheng-Bing Wu;Wei Qu;Yong Liang;Xiang-Tao Liu
在高维、大样本的大数据时代，最小绝对收缩和选择算子（LASSO）问题需要高效的算法。最近提出了基于筛选测试原理的静态和动态策略，以便安全地从字典中过滤掉不相关的原子。然而，此类策略仅适用于正则化参数较大的 LASSO 问题，而对于正则化参数较小的 LASSO 问题则效率较低。本文提出了一种新颖的贪婪筛选测试策略，以加速解决具有较小正则化参数的 LASSO 问题，以及通过采用相对较大的正则化参数在每次迭代中过滤掉不相关原子的有效性。进一步给出了贪心策略的收敛性证明，并研究了与该策略集成的LASSO求解器的计算复杂度。在合成数据集和真实数据集上的数值实验都支持了这种贪婪策略的有效性，结果表明，对于具有小正则化参数的 LASSO 问题，它的性能优于静态和动态策略。
In the era of big data remarked by high dimensionality and large sample size, the least absolute shrinkage and selection operator (LASSO) problems demand efficient algorithms. Both static and dynamic strategies based on screening test principle have been proposed recently, in order to safely filter out irrelevant atoms from the dictionary. However, such strategies only work well for LASSO problems with large regularization parameters, and lose their efficiency for those with small regularization parameters. This paper presents a novel greedy screening test strategy to accelerate solving LASSO problems with small regularization parameters, as well as its effectiveness through adoption of a relatively larger regularization parameter which filters out irrelevant atoms in every iteration. Further more, the convergence proof of the greedy strategy is given, and the computational complexity of LASSO solvers integrated with this strategy is investigated. Numerical experiments on both synthetic and real data sets support the effectiveness of this greedy strategy, and the results show it outperforms both the static and dynamic strategies for LASSO problems with small regularization parameters.