• Topics:
• Big Data
• Empirical Risk Minimization

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:
  
  @inproceedings{lei2017doublygre, author = "Qi Lei AND Ian En-Hsu Yen AND Chao-yuan Wu AND Pradeep Ravikumar AND Inderjit S. Dhillon", title = "Doubly Greedy Primal-Dual Coordinate Methods for Sparse Empirical Risk Minimization", booktitle = "International Conference on Machine Learning (ICML)", page = "8", year = "2017", month = "aug", 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" }