Stochastic Mirror Descent Algorithm for L1-Regularized Risk Minimizations

L1-regularized empirical risk minimization is a popular method for feature selections. In this paper we propose a fast online algorithms for solving large-scale L1-regularized problems. The proposed stochastic mirror descent algorithm is a stochastic version of the mirror-prox method. We show that mirror descent is a unified framework of several recently proposed algorithms. Experiments on large-scale datasets demonstrate that the proposed SMD algorithm is much faster than the recently proposed truncated gradient algorithm (TG). At the same testing accuracy, SMD yields sparser solutions than TG, while at the same sparseness, SMD has a higher testing accuracy.