TY - GEN
T1 - Doubly greedy primal-dual coordinate descent for sparse empirical risk minimization
AU - Lei, Qi
AU - Yen, Ian E.H.
AU - Wu, Chao Yuan
AU - Dhillon, Inderjit S.
AU - Ravikumar, Pradeep
N1 - Funding Information:
I.D. acknowledges the support of NSF via CCF-1320746, IIS-1546452, and CCF-1564000. P.R. acknowledges the support of ARO via W91 INF-12-1-0390 and NSF via IIS-1149803, IIS-1320894, IIS-1447574, and DMS-1264033, and NIH via ROI GM117594-01 as part of the Joint DMS/NIGMS Initiative to Support Research at the Interface of the Biological and Mathematical Sciences.
Publisher Copyright:
© 2017 by the author(s).
PY - 2017
Y1 - 2017
N2 - 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 Primal-Dual 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.
AB - 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 Primal-Dual 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.
UR - http://www.scopus.com/inward/record.url?scp=85048511868&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048511868&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85048511868
T3 - 34th International Conference on Machine Learning, ICML 2017
SP - 3191
EP - 3206
BT - 34th International Conference on Machine Learning, ICML 2017
PB - International Machine Learning Society (IMLS)
T2 - 34th International Conference on Machine Learning, ICML 2017
Y2 - 6 August 2017 through 11 August 2017
ER -