Parallel Lasso Screening for Big Data Optimization
Parallel Lasso Screening for Big Data Optimization
复制标题
DOI：
10.1145/2939672.2939859
复制
发表时间：
2016-08
期刊：
影响因子：
--
通讯作者：
Qingyang Li;Shuang Qiu;Shuiwang Ji;P. Thompson;Jieping Ye;Jie Wang
中科院分区：
文献类型：
--
作者：
Qingyang Li;Shuang Qiu;Shuiwang Ji;P. Thompson;Jieping Ye;Jie Wang
套索回归是数据挖掘中用于模型选择和特征提取的一种广泛使用的技术。在许多应用中，将回归模型应用于具有高维特征的海量数据样本的大规模问题仍然具有挑战性。一种流行且前景看好的策略是并行解决套索问题。并行求解器在一个共享存储系统上并行运行多个核以加速计算，但由于特征空间的巨大维度限制了其实际应用。筛选是一种很有前途的解决高维问题的方法，它通过丢弃不活跃的特征并将它们从优化中去除。然而，当筛选方法与并行求解器相结合时，大多数求解器不能保证在约简特征矩阵上的收敛。在本文中，我们通过并行化筛选方法并将其与我们提出的并行求解器相结合，提出了一种新的并行框架。提出了两种并行筛选算法：并行强规则算法(PSR)和并行双多面体投影算法(PDPP)。对于并行求解器，我们提出了一种异步分组坐标下降法(AGCD)来并行优化约简特征矩阵上的回归问题。AGCD基于分组选择策略，在一组候选者中选择对目标函数具有最大降幅的坐标。在真实数据集上的实验研究表明，与最先进的并行求解器相比，该并行框架具有更好的性能。
Lasso regression is a widely used technique in data mining for model selection and feature extraction. In many applications, it remains challenging to apply the regression model to large-scale problems that have massive data samples with high-dimensional features. One popular and promising strategy is to solve the Lasso problem in parallel. Parallel solvers run multiple cores in parallel on a shared memory system to speedup the computation, while the practical usage is limited by the huge dimension in the feature space. Screening is a promising method to solve the problem of high dimensionality by discarding the inactive features and removing them from optimization. However, when integrating screening methods with parallel solvers, most of solvers cannot guarantee the convergence on the reduced feature matrix. In this paper, we propose a novel parallel framework by parallelizing screening methods and integrating it with our proposed parallel solver. We propose two parallel screening algorithms: Parallel Strong Rule (PSR) and Parallel Dual Polytope Projection (PDPP). For the parallel solver, we proposed an Asynchronous Grouped Coordinate Descent method (AGCD) to optimize the regression problem in parallel on the reduced feature matrix. AGCD is based on a grouped selection strategy to select the coordinate that has the maximum descent for the objective function in a group of candidates. Empirical studies on the real-world datasets demonstrate that the proposed parallel framework has a superior performance compared to the state-of-the-art parallel solvers.