Asynchronous Parallel Greedy Coordinate Descent | Center for Big Data Analytics

Abstract: In this paper, we propose and study an Asynchronous parallel Greedy Coordinate Descent (Asy-GCD) algorithm for minimizing a smooth function with bounded constraints. At each iteration, workers asynchronously conduct greedy coordinate descent updates on a block of variables. In the first part of the paper, we analyze the theoretical behavior of Asy-GCD and prove a linear convergence rate. In the second part, we develop an efficient kernel SVM solver based on Asy-GCD in the shared memory multi-core setting. Since our algorithm is fully asynchronous—each core does not need to idle and wait for the other cores—the resulting algorithm enjoys good speedup and outperforms existing multi-core kernel SVM solvers including asynchronous stochastic coordinate descent and multi-core LIBSVM.

Download: pdf

Citation

Asynchronous Parallel Greedy Coordinate Descent (pdf, software)
Y. You, X. Lian, J. Liu, H. Yu, I. Dhillon, J. Demmel, C. Hsieh.
In Neural Information Processing Systems (NIPS), December 2016.

Bibtex:
@inproceedings{you2016asynchrono, author = "Yang You AND Xiangru Lian AND Ji Liu AND Hsiang-Fu Yu AND Inderjit S. Dhillon AND James Demmel AND Cho-Jui Hsieh", title = "Asynchronous Parallel Greedy Coordinate Descent", booktitle = "Neural Information Processing Systems (NIPS)", year = "2016", month = "dec", abstract = "In this paper, we propose and study an Asynchronous parallel Greedy Coordinate Descent (Asy-GCD) algorithm for minimizing a smooth function with bounded constraints. At each iteration, workers asynchronously conduct greedy coordinate descent updates on a block of variables. In the first part of the paper, we analyze the theoretical behavior of Asy-GCD and prove a linear convergence rate. In the second part, we develop an efficient kernel SVM solver based on Asy-GCD in the shared memory multi-core setting. Since our algorithm is fully asynchronous—each core does not need to idle and wait for the other cores—the resulting algorithm enjoys good speedup and outperforms existing multi-core kernel SVM solvers including asynchronous stochastic coordinate descent and multi-core LIBSVM." }