Abstract: We consider the popular problem of sparse empirical
risk minimization with linear predictors and
a large number of both features and observations.
With a convex-concave saddle point objective reformulation,
we propose a Doubly Greedy PrimalDual
Coordinate Descent algorithm that is able to
exploit sparsity in both primal and dual variables.
It enjoys a low cost per iteration and our theoretical
analysis shows that it converges linearly
with a good iteration complexity, provided that
the set of primal variables is sparse. We then extend
this algorithm further to leverage active sets.
The resulting new algorithm is even faster, and
experiments on large-scale Multi-class data sets
show that our algorithm achieves up to 30 times
speedup on several state-of-the-art optimization
methods
Download: pdf
Citation
- Doubly Greedy Primal-Dual Coordinate Methods for Sparse Empirical Risk Minimization (pdf, software)
Q. Lei, I. Yen, C. Wu, P. Ravikumar, I. Dhillon.
In International Conference on Machine Learning (ICML), pp. 8, August 2017.
Bibtex: