一种求解截断L1正则化项问题的坐标下降算法

L1正则化在稀疏学习的研究中起关键作用，使用截断L1正则化项往往可以获得更好的准确率，但却导致了非凸优化问题.目前，主要采用多阶段凸松弛(multi-stage convex relaxation, MSCR)算法进行求解，由于每一阶段都需要求解一个凸优化问题，计算代价较大.为了弥补上述不足，提出了一种求解截断L1正则化项非凸学习问题的坐标下降算法(Non-convex CD).该算法只需在多阶段凸松弛算法的每一阶段执行单步的坐标下降算法，有效降低了计算复杂性.理论分析表明所提出的算法是收敛的.针对Lasso问题，在大规模真实数据库作了实验，实验结果表明，Non-convex CD在取得和MSCR几乎相同准确率的基础上，求解的CPU时间甚至优于求解凸问题的坐标下降方法.为了进一步说明所提算法的性能，进一步研究了Non-convex CD在图像去模糊化中的应用问题.

A Coordinate Descent Algorithm for Solving Capped-L1 Regularization Problems

L1 regularization plays a crucial role in sparse learning and higher accuracy can be achieved by using the capped-L1 regularization. However, it leads to a non-convex optimization problem, which is currently solved by a multi-stage convex relaxation algorithm (MSCR). As a convex optimization problem has to be solved exactly at each stage, extra computational cost can not be avoided in MSCR. In order to circumvent this drawback, in this paper, a new non-convex coordinate descent algorithm (Non-convex CD) is presented for solving the capped-L1 regularization problems, in which only one single-step of regular coordinate descent is employed in each stage of MSCR. Such a Non-convex CD can effectively reduce the computational cost. Theoretical analysis shows convergence of the proposed algorithm. For the commonly Lasso problems, the experiments on large-scale text databases demonstrate that Non-convex CD spends even less CPU time than the regular coordinate descent method, while keeping almost the same accuracy as MSCR. To further illustrate the high performance of Non-convex CD in real application, we also consider an image deblurring example.