求解大规模SCAD回归问题的随机坐标下降算法研究

回归方法是重要的数据分析工具。带平滑削边绝对偏离(smoothly clipped absolute deviation, SCAD)正则项的回归问题,以其在处理高维数据中的近似无偏性(见Fan和Li,2001),在大数据分析中得到广泛应用。但在大数据背景下,待求解的SCAD回归问题的数据量往往很大,而且分布在不同地理位置,这使得在SCAD回归问题的求解算法设计中,需要重新考虑计算的内存使用量。常规用于求解SCAD回归问题的优化算法(LQA、LLA、ADMM等)往往需要在每一次迭代中更新全部变量,从而造成计算的内存需求很大,难以适应大数据的求解要求。随机坐标下降方法(stochastic coordinate descent, SCD)以其子问题运算内存需求小(见Nesterov,2012)的优势,在大规模分布式最优化问题中得到了广泛的应用。但目前理论上SCD算法仅能处理带凸惩罚项的回归问题,由于SCAD回归问题中惩罚项的非凸非光滑性,现有的随机坐标下降方法难以处理这一问题。首先对SCAD回归问题模型进行分析,得出SCAD回归模型的损失函数是导数Lipschitz、惩罚函数是semi-convex的,此外根据已有结论,得到SCAD回归问题的稳定点即可保证良好的统计性质。基于这些性质的分析,介绍了一种新的随机坐标下降方法(variable bregman stochastic coordinate descent, VBSCD),这一方法能很好求解带SCAD惩罚项的回归问题,算法的收敛点是SCAD回归模型的稳定点。最后,通过计算实验进一步说明本算法在求解SCAD回归问题的有效性。对不同的变量分组数,算法迭代到稳定点所需的迭代回合数相对稳定。随着变量分块数的增加,单次迭代中计算的内存需求减少。该研究方法可广泛应用于大数据背景下SCAD回归问题的求解当中。

求解大型线性最小二乘问题的贪婪Gauss-Seidel方法

基于一种选择系数矩阵A的工作列的策略,提出了求解大型线性最小二乘问题的一种不同的贪婪Gauss-Seidel方法,并对该方法进行了收敛性分析。数值实验表明,在相同的精度下,所提方法在计算时间上优于文献提出的贪婪随机坐标下降方法。