THE CONFERENCE
FOR AUTHORS
FOR PARTICIPANTS

 
Talk
Doubly Greedy Primal-Dual Coordinate Descent for Sparse Empirical Risk Minimization
Qi Lei · En-Hsu Yen · Chao-Yuan Wu · Inderjit Dhillon · Pradeep Ravikumar

Mon Aug 7th 04:06 -- 04:24 PM @ Parkside 2
in Continuous optimization 3 »

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.

Author Information

Qi Lei (University of Texas at Austin)
Ian Yen (Carnegie Mellon University)

I am currently a PhD student in the Computer Science School of Carnegie Mellon University (Machine Learning Department), working with Pradeep Ravikumar and Inderjit Dhillon. I received my B.S./B.B.A/M.S. from CSIE/IM departments of National Taiwan University, where I worked with Shou-De Lin. My research focuses on Large-Scale Machine Learning, Convex Optimization and their applications.

Chao-Yuan Wu (UT Austin)
Inderjit Dhillon (UT Austin & Amazon)

Inderjit Dhillon is the Gottesman Family Centennial Professor of Computer Science and Mathematics at UT Austin, where he is also the Director of the ICES Center for Big Data Analytics. His main research interests are in big data, machine learning, network analysis, linear algebra and optimization. He received his B.Tech. degree from IIT Bombay, and Ph.D. from UC Berkeley. Inderjit has received several awards, including the ICES Distinguished Research Award, the SIAM Outstanding Paper Prize, the Moncrief Grand Challenge Award, the SIAM Linear Algebra Prize, the University Research Excellence Award, and the NSF Career Award. He has published over 160 journal and conference papers, and has served on the Editorial Board of the Journal of Machine Learning Research, the IEEE Transactions of Pattern Analysis and Machine Intelligence, Foundations and Trends in Machine Learning and the SIAM Journal for Matrix Analysis and Applications. Inderjit is an ACM Fellow, an IEEE Fellow, a SIAM Fellow and an AAAS Fellow.

Pradeep Ravikumar (Carnegie Mellon University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors