一种基于Comid的非光滑损失随机坐标下降方法

坐标下降方法以简洁的操作流程、低廉的计算代价和快速的实际收敛效果,成为处理大规模优化最有效的方法之一.但目前几乎所有的坐标下降方法都由于子问题解析求解的需要而假设损失函数的光滑性.本文在结构学习的框架下,在采用Comid方法求解随机挑选单变量子问题的基础上,提出了一种新的关于非光滑损失的随机坐标下降方法.理论分析表明本文所提出的算法在一般凸条件下可以得到Ο(√t/t)的收敛速度,在强凸条件下可以得到Ο(lnt/t)的收敛速度.实验结果表明本文所提出的算法对正则化Hinge损失问题实现了坐标优化预期的效果.

A New Comid-Based Stochastic Coordinate Descent Method for Non-Smooth Losses

Coordinate descent (CD) method is one of the most efficient algorithms in dealing with the large-scale optimization problems for its simple operation,cheap computational cost and practical efficiency.However until now,almost all the-state-of-art CD algorithms require the smoothness assumption of loss functions due to solving the subproblems in closed-form.In this paper,within the structural learning framework,we present a new stochastic CD(SCD)algorithm for non-smooth losses,in which the randomly selected single variable problem is solved using Comid method.Theoretical analysis indicates that the proposed algorithm has an O(√t/t) convergence rate for general convex problems and an O(lnt/t) convergence rate for strongly convex problems.The experiments demonstrate the expected efficiency of our SCD algorithms when coping with the L1-regularized Hinge loss problems.