Asynchronous Parallel Greedy Coordinate Descent
Yang You, Xiangru Lian, Ji Liu, Hsiang-Fu Yu, Inderjit S Dhillon, James Demmel, Cho-Jui Hsieh
Abstract
n 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.
BibTeX
@inproceedings{NIPS2016_43e4e6a6,
author = {You, Yang and Lian, Xiangru and Liu, Ji and Yu, Hsiang-Fu and Dhillon, Inderjit S and Demmel, James and Hsieh, Cho-Jui},
booktitle = {Advances in Neural Information Processing Systems},
editor = {D. Lee and M. Sugiyama and U. Luxburg and I. Guyon and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Asynchronous Parallel Greedy Coordinate Descent},
url = {https://proceedings.neurips.cc/paper_files/paper/2016/file/43e4e6a6f341e00671e123714de019a8-Paper.pdf},
volume = {29},
year = {2016}
}