Authors: Jialei Wang (Two Sigma), Jianqiao Wangni, Ji Liu, Tong Zhang
To be presented at: 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montréal, Canada
Abstract: Modern large-scale machine learning applications require stochastic optimization algorithms to be implemented on distributed computational architectures. A key bottleneck is the communication overhead for exchanging information such as stochastic gradients among different workers. In this paper, to reduce the communication cost, we propose a convex optimization formulation to minimize the coding length of stochastic gradients. The key idea is to randomly drop out coordinates of the stochastic gradient vectors and amplify the remaining coordinates appropriately to ensure the sparsified gradient to be unbiased. To solve the optimal sparsification efficiently, several simple and fast algorithms are proposed for an approximate solution, with a theoretical guarantee for sparseness. Experiments on ℓ2 regularized logistic regression, support vector machines, and convolutional neural networks validate our sparsification approaches.
