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-(1/2)/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.